摘要:

AbstractIn this article, we will determine the crossing number of the complete tripartite graphsK1,3,nandK2,3,n. Our proof depends on Kleitman's results for the complete bipartite graphs [D. J. Kleitman, The crossing number ofK5,n.J. Combinatorial Theory9 (1970) 315‐323

ISSN:0364-9024    

DOI:10.1002/jgt.3190100102

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

年代:1986

数据来源: WILEY

摘要:

AbstractAn explicit expression is derived for the connectivity of circulant digraphs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100103

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

年代:1986

数据来源: WILEY

摘要:

AbstractWe prove, by means of explicit bijections, theorems of Whitney and Stanley that express the coefficients of the chromatic polynomial of a graphGand the number of acyclic orientations ofGin terms of numbers of sets of edges that contain no broken circuits ofG.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100104

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

年代:1986

数据来源: WILEY

摘要:

AbstractLetTbe a trail of a graphG. Tis aspanning trail (S‐trail)ifTcontains all vertices ofG. Tis adominating trail (D‐trail)if every edge ofGis incident with at least one vertex ofT.Acircuitis a nontrivial closed trail. Sufficient conditions involving lower bounds on the degree‐sum of vertices or edges are derived for graphs to have an S‐trail, S‐circuit, D‐trail, or D‐circuit. Thereby a result of Brualdi and Shanny and one mentioned by Lesniak‐Foster and Williams

ISSN:0364-9024    

DOI:10.1002/jgt.3190100105

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

年代:1986

数据来源: WILEY

摘要:

AbstractThe Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true iff it is true on these restricted families. These appear to be the first results of this type.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100106

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

年代:1986

数据来源: WILEY

摘要:

AbstractWe show that the number of labeled (n, q)‐multigraphs with some specifiedpvertices of odd degree is asymptotically independent ofpand is in fact asymptotically 21−ntimes the number of (n, q)‐multigraphs. We determine the asymptotic number of (n, q)‐mult

ISSN:0364-9024    

DOI:10.1002/jgt.3190100107

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

年代:1986

数据来源: WILEY

摘要:

AbstractIf a 3‐regular graph has bipartite densityband independence ratioi, theni≥ (3b− 1)/4. A construction demonstrates that this is best possible for all admissible value

ISSN:0364-9024    

DOI:10.1002/jgt.3190100108

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

年代:1986

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190100109

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

年代:1986

数据来源: WILEY

摘要:

AbstractThe aim of this paper is to prove that any balanced caterpillar having 2nvertices and maximum degree 3 spans then‐dimensional hypercub

ISSN:0364-9024    

DOI:10.1002/jgt.3190100110

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

年代:1986

数据来源: WILEY

摘要:

AbstractWe consider in this paper graphs which remain hamiltonian after the removal ofkedges (k‐edge hamiltonian) orkvertices (k‐hamiltonian). These classes of graphs arise from reliability considerations in network design. In a previous paper, W. W. Wong and C. K. Wong presented families of minimumk‐hamiltonian graphs and minimumk‐edge hamiltonian graphs forkeven. Here, we complete this study in the case where

ISSN:0364-9024    

DOI:10.1002/jgt.3190100111

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

年代:1986

数据来源: WILEY