摘要:

AbstractFor a graphG, a subset of verticesDis a dominating set if for each vertex X not inD, X is adjacent to at least one vertex ofD.The domination number, γ(G), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graphGandH,\documentclass{article}\pagestyle{empty}\begin{document}$$ \gamma \left({{\rm G} \times {\rm H}} \right) \ge \gamma \left(G \right)\gamma \left(H \right) $$\end{document}One result presented in this paper settles this question in the case when at least one ofGorHis a tree. We show that\documentclass{article}\pagestyle{empty}\begin{document}$$ \gamma \left({G \times T} \right) \ge \gamma \left(G \right)\gamma \left(T \right) $$\end{document}for all graphsGand any treeT.Furthermore, we supply a partial characterization for which pairs of trees,T1andT2, strict inequality occurs. We show\documentclass{article}\pagestyle{empty}\begin{document}$$ \gamma \left({T_1 \times T_1 } \right)\gamma \left({T_1 } \right)\gamma \left({T_2 } \right) $$\end{document}for almost all pairs of trees

ISSN:0364-9024    

DOI:10.1002/jgt.3190100112

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractWe extend an elegant proof technique of A. G. Thomason, and deduce several parity theorems for paths and cycles in graphs. For example, a graph in which each vertex is of even degree has an even number of paths if and only if it is of even order, and a graph in which each vertex is of odd degree has an even number of paths if and only if its order is a multiple of four. Our results have implications for generalized friendship graphs and their conjectured nonexistence.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100113

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractA graphGis said to be decomposable ifGcan be decomposed into a cartesian product of two nontrivial graphs.Gis bidecomposable if not onlyGbut also its complementGis decomposable. We prove that there are only six bidecomposable graphs; 2K(2),C4,Q3,K(2) ×(K(2) +K(2)),K(3) ×K(3

ISSN:0364-9024    

DOI:10.1002/jgt.3190100114

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractWe show that every graphGonnvertices with minimal degree at leastn/kcontains a cycle of length at least [n/(k− 1)]. This verifies a conjecture of Katchalski. Whenk= 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2nthenGis Hamiltonia

ISSN:0364-9024    

DOI:10.1002/jgt.3190100115

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractWe show that a graphGwithnvertices is aq‐tree if and only if its chromatic polynomial isP(G, λ) = λ(λ – 1) ⃛ (λ –q+ 1) (λ

ISSN:0364-9024    

DOI:10.1002/jgt.3190100116

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190100101

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY