摘要:

AbstractThe generalized Petersen graphGP(n, k),n≤ 3, 1 ≥k

ISSN:0364-9024    

DOI:10.1002/jgt.3190190102

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe graphK5‐eis obtained from the complete graphK5by deleting one edge, whileK1+C4is obtained fromK5by deleting two independent edges. With the help of a computer it is shown thatr(K1+C4,K5‐e) = 17. © 1995 John Wiley&Sons,

ISSN:0364-9024    

DOI:10.1002/jgt.3190190103

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

年代:1995

数据来源: WILEY

摘要:

AbstractFor the maximum numberf(n) of edges in aC4‐free subgraph of then‐dimensional cube‐graphQnwe provef(n) ≥ 1/2(n +√n)2n−1forn= 4r, andf(n) ≥ 1/2(n +0.9√n)2n−1for alln≥ 9. This disproves one version of a conjecture of P. Erdos. © 1995

ISSN:0364-9024    

DOI:10.1002/jgt.3190190104

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

年代:1995

数据来源: WILEY

摘要:

AbstractA (finite or infinite) graphGis retract‐collapsible if it can be dismantled by deleting systematically at each step every vertex that is strictly dominated, in such a way that the remaining subgraph is a retract ofG, and so as to get a simplex at the end. A graph is subretract‐collapsible if some graph obtained by planting some rayless tree at each of its vertices is retract‐collapsible. It is shown that the subretract‐colapsible graphs are cop‐win; and that a ball‐Helly graph is subretract‐collapsible if and only if it has no isometric infinite paths (thus in particular if it has no infinite paths, or if it is bounded). Several fixed subgraph properties are proved. In particular, ifGis a subretract‐collapsible graph, andfa contraction fromGintoG, then (i) ifGhas no infinite simplices, thenf(S) =Sfor some simplexSofG; and (ii) if the dismantling ofGcan be achieved in a finite number of steps and if some family of simplices ofGhas a compacity property, then there is a simplexSofGsuch thatf(S) ⊆S. This last result generalizes a property of bounded ball‐Helly graphs. © 1995

ISSN:0364-9024    

DOI:10.1002/jgt.3190190105

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe examine bounds on the size of the neighborhood union for two (independent) vertices of a graph that imply the existence of regular factors. © 1995 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190190106

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe following is proved: if every bridgeless graphGhas a cycle cover of length at most 7/5|E(G)|, then every bridgeless graphGhas a cycle cover of length at most 7/5|E(G)| such that any edge ofGis covered once or twice. © 1995 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190190107

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

年代:1995

数据来源: WILEY

摘要:

AbstractA well‐covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1‐well‐covered graph was introduced by Staples in her 1975 dissertation: a well‐covered graphGis 1‐well‐covered if and only ifG‐vis also well covered for every pointvinG. Except forK2andC5, every 1‐well‐covered graph contains triangles or 4‐cycles. We show that all planar 1‐well‐covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family. © 1

ISSN:0364-9024    

DOI:10.1002/jgt.3190190108

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

年代:1995

数据来源: WILEY

摘要:

AbstractA total dominating function (TDF) of a graphG= (V, E) is a functionf:V← [0, 1] such that for eachvϵ V, ΣuϵN(v)f(u) ≥ 1 (whereN(v) denotes the set of neighbors of vertexv). Convex combinations of TDFs are also TDFs. However, convex combinations of minimal TDFs (i.e., MTDFs) are not necessarily minimal.In this paper we discuss the existence in trees of a universal MTDF (i.e., an MTDF whose convex combinations with any other MTDF are also minimal). © 1995 John Wiley&So

ISSN:0364-9024    

DOI:10.1002/jgt.3190190109

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

年代:1995

数据来源: WILEY

摘要:

AbstractA regular multigraph with maximum multiplicityrand degreerscannot always be factored intor s‐regular simple graphs. It is shown, however, that under general conditions a similar factorization can be achieved if we first allow the addition or deletion of a relatively small number of hamilton cycles. Based on this result, we give extensions of some known factorization results on simple graphs to new results on multigraphs. © 1995 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190190110

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn this article we give examples of a triangle‐free graph on 22 vertices with chromatic number 5 and aK4‐free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5‐critical graphs on 9 vertices are exhibited. © 1995 John Wiley&Son

ISSN:0364-9024    

DOI:10.1002/jgt.3190190111

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

年代:1995

数据来源: WILEY