摘要:

AbstractThe paper contains a proof of the conjecture of Harary and Plantholt, stated in the title.

ISSN:0364-9024    

DOI:10.1002/jgt.3190140102

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

年代:1990

数据来源: WILEY

摘要:

AbstractThe spectrum of numbers of repeated edges in 2‐factorizations of 2Knis determined for alln.The techniques employed are direct, using isomorphic factorizations of Kn, and closely related factorization

ISSN:0364-9024    

DOI:10.1002/jgt.3190140103

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

年代:1990

数据来源: WILEY

摘要:

AbstractLet

ISSN:0364-9024    

DOI:10.1002/jgt.3190140104

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

年代:1990

数据来源: WILEY

摘要:

AbstractA classical theorem of Hassler Whitney asserts that any maximal planar graph with no separating triangles is Hamiltonian. In this paper, we examine the problem of generalizing Whitney's theorem by relaxing the requirement that the triangulation be a maximal planar graph (i.e., that its outer boundary be a triangle) while maintaining the hypothesis that the triangulation have no separating triangles. It is shown that the conclusion of Whitney's theorem still holds if the chords satisfy a certain sparse‐ness condition and that a Hamiltonian cycle through a graph satisfying this condition can be found in linear time. Upper bounds on the shortness coefficient of triangulations without separating triangles are established. Several examples are given to show that the theorems presented here cannot be extended without strong additional hypotheses. In particular, a 1‐tough, non‐Hamiltonian triangulation with no separating triangles is pres

ISSN:0364-9024    

DOI:10.1002/jgt.3190140105

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

年代:1990

数据来源: WILEY

摘要:

AbstractB. Jackson [4] made the following conjecture: IfGis an Eulerian graph with δ(G) ≥ 2k, thenGhas a set of 2k‐ 2 pairwise compatible Euler cycles (i.e., every pair of adjacent edges appears in at most one of these Euler cycles as a pair of consecutive edges). We verify this conjecture in the case where every circuit ofGis a block

ISSN:0364-9024    

DOI:10.1002/jgt.3190140106

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe determine the minimum number of edges in a regular connected graph onnvertices, containing a complete subgraph of orderk≤n/2. This enables us to confirm and strengthen a conjecture of P. Erdös on the existence of regular graphs with prescribed chromatic numb

ISSN:0364-9024    

DOI:10.1002/jgt.3190140107

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe prove in this note that the linear vertex‐arboricity of any planar graph is at most three, which confirms a conjecture due to Broere and Mynhardt, and other

ISSN:0364-9024    

DOI:10.1002/jgt.3190140108

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

年代:1990

数据来源: WILEY

摘要:

AbstractA graphHiscollapsibleif for every subset X ⊆V(H), Hhas a spanning connected subgraph whose set of odd‐degree vertices is X. In any graphGthere is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction ofGis areducedgraph. Interest in reduced graphs arises from the fact [4] that a graphGhas a spanning closed trail if and only if its corresponding reduced graph has a spanning closed trail. The concept can also be applied to study hamiltonian line graphs [11] or double cycle covers [8]. In this article, we characterize the reduced graphs of diameter two. As applications, we obtain prior results in [12] and [14], and show that every 2‐edge‐connected graph with diameter at most two either admits a double cycle cover with three even subgraphs or is isomorphic to the Peterse

ISSN:0364-9024    

DOI:10.1002/jgt.3190140109

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

年代:1990

数据来源: WILEY

摘要:

AbstractLetK(p, q), p ≤ q, denote the complete bipartite graph in which the two partite sets consist ofpandqvertices, respectively. In this paper, we prove that (1) the graphK(p, q)is chromatically unique ifp≥ 2; and (2) the graphK(p, q)‐eobtained by deleting an edgeefromK(p, q)is chromatically unique ifp≥ 3. The first result was conjectured by Salzberg, López, and Giudici, who also proved the second result under the condition that

ISSN:0364-9024    

DOI:10.1002/jgt.3190140110

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

年代:1990

数据来源: WILEY

摘要:

AbstractIn this paper we obtain chromatic polynomials of connected 3‐ and 4‐chromatic planar graphs that are maximal for positive integer‐valued arguments. We also characterize the class of connected 3‐chromatic graphs having the maximum number ofp‐colorings forp≥ 3, thus extending a previous result by the author (th

ISSN:0364-9024    

DOI:10.1002/jgt.3190140111

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

年代:1990

数据来源: WILEY