摘要:

AbstractA well‐known conjecture in hamiltonian graph theory states that every 2‐tough graph is hamiltonian. We give some equivalent conjectures, e.g., the conjecture that every 2‐tough graph is hamiltonian‐co

ISSN:0364-9024    

DOI:10.1002/jgt.3190180602

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

年代:1994

数据来源: WILEY

摘要:

AbstractLetMbe a map on a surfaceS. The edge‐width ofMis the length of a shortest noncontractible cycle ofM. The face‐width (or, representativity) ofMis the smallest number of intersections a noncontractible curve inShas withM. (The edge‐width and face‐width of a planar map may be defined to be infinity.) A map is a large‐edge‐width embedding (LEW‐embedding) if its maximum face valency is less than its edge‐width. For several families of rooted maps on a given surface, we prove that there are positive constantsC1andC2, depending on the family and the surface, such that1almost all maps withnedges have face‐width and edge‐width greater thanc1logn, and2the fraction of such maps that are LEW‐embeddings and the fraction that are not LEW‐embe

ISSN:0364-9024    

DOI:10.1002/jgt.3190180603

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn a fundamental paper, G. Sabidussi [“Graph Multiplication,” Mathematische Zeitschrift, Vol. 72 (1960), pp. 446–457] used a tower of equivalence relations on the edge setE(G) of a connected graphGto decomposeGinto a Cartesian product of prime graphs. Later, a method by R.L. Graham and P.M. Winkler [“On Isometric Embeddings of Graphs,”Transactions of the American Mathematics Society, Vol. 288 (1985), pp. 527–533] of embedding a connected graph isometrically into Cartesian products opened another approach to this problem. In both approaches an equivalence relation σ that determines the prime factorization is constructed. The methods differ by the starting relations used. We show that σ can be obtained as the convex hull of the starting relation used by Sabidussi. Our result also holds for the relation determining the prime decomposition of infinite connected graphs with respect to the weak Cartesian product. Moreover, we show that this relation is the transitive closure of the union of the starting relations of Sabidussi and Winkler [“Factoring a Graph in Polynomial Time,”European Journal of Combinatorics, Vol. 8 (1987), pp. 209–212], thereby generalizing the result of T. Feder [“Product Graph Representations,”Journal of Graph Theory, Vol 16 (1993), pp. 467–488] from

ISSN:0364-9024    

DOI:10.1002/jgt.3190180604

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe show that the game chromatic number of a planar graph is at most 33. More generally, there exists a functionf: ℕ → ℕ so that for eachn∈ ℕ, if a graph does not contain a homeomorph ofKn, then its game chromatic number is at mostf(n). In particular, the game chromatic number of a graph is bounded in terms of its genus. Our proof is motivated by the concept ofp‐arrangeability, which was first introduced by Guantao and Schelp in a Ramsey theore

ISSN:0364-9024    

DOI:10.1002/jgt.3190180605

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

年代:1994

数据来源: WILEY

摘要:

AbstractA triangle‐free graph is maximal if adding any edge will create a triangle. The minimal number of edges of a maximal triangle‐free graph onnvertices having maximal degree at most D is denoted byF(n, D). We determine the value of limn‐∞F(n,cn)/nfor 2/5

ISSN:0364-9024    

DOI:10.1002/jgt.3190180606

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

年代:1994

数据来源: WILEY

摘要:

AbstractLetG1,G2,. …,Gtbe an arbitraryt‐edge coloring ofKn, where for eachi∈ {1,2, …,t},Giis the spanning subgraph ofKnconsisting of all edges colored with theith color. The irredundant Ramsey numbers(q1,q2, …,qt) is defined as the smallest integernsuch that for anyt‐edge coloring ofKn,ihas an irredundant set of sizeqifor at least onei∈ {1,2, …,t}. It is proved that s(3,3,3) = 13, a result that improves the known bounds 12

ISSN:0364-9024    

DOI:10.1002/jgt.3190180607

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this article we determine the crossing numbers of the Cartesian products of graphs on four vertices with paths and stars.

ISSN:0364-9024    

DOI:10.1002/jgt.3190180608

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

年代:1994

数据来源: WILEY

摘要:

AbstractA graph isfraternally orientediff for every three verticesu, ν,wthe existence of the edgesu→wand ν →wimplies thatuand ν are adjacent. Adirected unicyclic graphis obtained from a unicyclic graph by orienting the unique cycle clockwise and by orienting the appended subtrees from the cycle outwardly. Two directed subtreess, tof a directed unicyclic graph areproperif their union contains no (directed or undirected) cycle and either they are disjoint or one of themshas its rootr(s) intand contains all the successors ofr(s) int.In the present paper we prove thatGis an intersection graph of a family of proper directed subtrees of a directed unicyclic graph iff it has a fraternal orientation such that for every vertexν, G(Γinν) is acyclic and G(Γoutν) is the transitive closure of a tree. We describe efficient algorithms for recognizing when such graphs are perfect and for testing isomorphism of proper circular

ISSN:0364-9024    

DOI:10.1002/jgt.3190180609

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

年代:1994

数据来源: WILEY

摘要:

AbstractFor anys≥ 1 andt≥ (S2), we prove that among all graphs withnvertices the graph that contains the maximal number of induced copies ofKt,t+sfor any fixeds≥ 1 andt≥ (s2) isK(n/2)+α(n/2)‐αfor some function α =o(n). We show that this is not valid fort<(s2). Analogous results for complete multipartite graphs are a

ISSN:0364-9024    

DOI:10.1002/jgt.3190180610

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

年代:1994

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190180601

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

年代:1994

数据来源: WILEY