摘要:

AbstractIn this article, we prove that a 5‐connected toroidal triangulation has a contractible Hamilton cycle. © 1995 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190200303

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

年代:1995

数据来源: WILEY

摘要:

AbstractMadar conjectured that everyk‐criticaln‐connected non‐complete graphGhas (2k+ 2) pairwise disjoint fragments. We show that Mader's conjecture holds if the order ofGis greater than (k+ 2)n. From this, it implies that two other conjectures onk‐criticaln‐connected graphs posed by Entringer, Slater, and Mader also hold if the cardinality of the graphs is large. © 1995 John Wiley

ISSN:0364-9024    

DOI:10.1002/jgt.3190200304

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe orientable genus is determined for any graph that embeds into the projective plane, Σ, to be essentially half of the representativity of any embedding into Σ. In addition, a structure is given for any 3‐connected projective planar graph as the union of a spanning planar graph and a variation of a Möbius Ladder. © 1995 John Wiley&Sons

ISSN:0364-9024    

DOI:10.1002/jgt.3190200305

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe study a class of perfect graphs which, because they generalize interval graphs, we call pseudo‐interval graphs. Like interval graphs, their vertices correspond to intervals of a linearly ordered set, but a modified definition of intersection is used in order to determine edges. The complements of pseudo‐interval graphs are comparability graphs but unlike interval graphs, pseudo‐interval graphs are only weakly triangulated. We characterize trees and complements of trees which are pseudo‐interval graphs. Finally we determine all minimal non‐pseudointerval graphs on eight or fewer vertices whose complements are comparability graphs and which are weakly triangulated. © 1995 John Wiley

ISSN:0364-9024    

DOI:10.1002/jgt.3190200306

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

年代:1995

数据来源: WILEY

摘要:

AbstractThis note gives a simple proof of a formula due to Bollobás, Frank and Karoński for counting acyclic bipartit tournaments. © 1995 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190200307

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe prove a necessary and sufficient condition for a regular bipartite multigraph to contain a 1‐factor including one specified set of independent edges and avoiding another specified set of edges. © 1995 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190200308

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn a recent paper, Barnette showed that every 3‐connected planar graph has a 2‐connected spanning subgraph of maximum degree at most fifteen, he also constructed a planar triangulation that does not have 2‐connected spanning subgraphs of maximum degree five. In this paper, we show that every 3‐connected graph which is embeddable in the sphere, the projective plane, the torus or the Klein bottle has a 2‐connected spanning subgraph of maximum degree at most six. © 1995 John Wiley

ISSN:0364-9024    

DOI:10.1002/jgt.3190200309

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

年代:1995

数据来源: WILEY

摘要:

AbstractIt is known thtMooredigraphs of degreed>1 and diameterk>1 do not exist (see [20] or [5]). Furthermore, for degree 2, it is shown tht forl≥ 3 there are no digraphs of order “close” to, i.e., one less thanMoorebound [18]. In this paper, we shall consider digraphs of diameterk, degree 3 and number of vertices one less thanMoorebound. We give a necessary condition for the existence of such digraphs and, using this condition, we deduce that such digraphs do not exist for infinitely many values of the diameter. © 1995 John Wiley&Son

ISSN:0364-9024    

DOI:10.1002/jgt.3190200310

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn this paper we present a relatively simple proof of Tutt's characterization of graphic matroids. The proof uses the notion of ‘signed graph’ and it is ‘graphic’ in the sense that it can be presented almost entirely by drawing (signed) graphs. © 1995 John Wiley&S

ISSN:0364-9024    

DOI:10.1002/jgt.3190200311

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila‐Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. © 1995 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190200312

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

年代:1995

数据来源: WILEY