摘要:

AbstractThe following results are proved in this paper. LetGbe a 2k‐edge‐connected eulerian graph. (i) For every set {e1,e2, ⃛,e2k+1} ⊆E(G) there is an eulerian trailTof the forme1,e2, ⃛,e2k+1, ⃛. (ii) For every setE* = {e1,e2, ⃛,ek} ⊆E(G) there is an eulerian trailT=e1, ⃛,e2, ⃛,ek, ⃛ in which the elements ofE* are traversed in accordance with a prescribed orientation. © 199

ISSN:0364-9024    

DOI:10.1002/jgt.3190190202

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

年代:1995

数据来源: WILEY

摘要:

AbstractGraph bundles generalize the notion of covering graphs and products of graphs. Several results about the chromatic numbers of graph bundles based on the Cartesian product, the strong product and the tensor product are presented. © 1995 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190190203

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

年代:1995

数据来源: WILEY

摘要:

AbstractLetGbe a 2‐connected graph onnvertices with maximum degreekwheren≤ 3k‐ 2. We show that there is a cycle inGthat contains all vertices of degreek.© 1995 John Wiley&Son

ISSN:0364-9024    

DOI:10.1002/jgt.3190190204

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn this paper we use the Hilton method of amalgamations to give a different proof of a theorem of Nash‐Williams that finds necessary and sufficient conditions for the embedding of an edge‐coloredKvinto an edge‐coloredKvin which the edges of each color induce a 2‐edge‐connectedk‐factor. © 1995 John Wil

ISSN:0364-9024    

DOI:10.1002/jgt.3190190205

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

年代:1995

数据来源: WILEY

摘要:

AbstractA tree is even if its edges can be colored in two colors so that the monochromatic subgraphs are isomorphic. All even trees of maximum degree 3 in which no two vertices of degrees 1 or 3 are adjacent are determined. It is also shown that, for everyn, there are only finitely many trees of maximum degree 3 and withnvertices of degree 3 that are not even. © 1995 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190190206

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

年代:1995

数据来源: WILEY

摘要:

AbstractLetT= (V, E) be a tree whose vertices are properly 2‐colored. A bipartite labeling ofTis a bijectionf:V← {0, 1, ⃛, |E|} for which there is aksuch that wheneverf(u) ≤k

ISSN:0364-9024    

DOI:10.1002/jgt.3190190207

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

年代:1995

数据来源: WILEY

摘要:

AbstractGiven a tournamentT, thetournament gameonTis as follows: Two players independently pick a node ofT.If both pick the same node, the game is tied. Otherwise, the player whose node is at the tail of the arc connecting the two nodes wins. We show that the optimal mixed strategy for this game is unique and uses an odd number of nodes.A tournament ispositiveif the optimal strategy for its tournament game uses all of its nodes. The uniqueness of the optimal strategy then gives a new tournament decomposition: any tournament can be uniquely partitioned into positive subtournamentsP1,P2, ⃛,Pk, soPi“beats”Pjfor all 1 ≤i>j≤k.We count the number ofnnode positive tournaments and list them forn≤ 7. © 1995 John Wil

ISSN:0364-9024    

DOI:10.1002/jgt.3190190208

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

年代:1995

数据来源: WILEY

摘要:

AbstractA cycle in a graph is a set of edges that covers each vertex an even number of times. A cocycle is a collection of edges that intersects each cycle in an even number of edges. A bicycle is a collection of edges that is both a cycle and a cocycle. The cycles, cocycles, and bicycles each form a vector space over the integers modulo two when addition is defined as symmetric difference of sets. In this paper we examine the relationship between the left‐right paths in a planar graph and the cycle space, cocylce space, and bicycle space. We show that planar graphs are characterized by the existence of a diagonal—a double cover by tours that interacts with the cycle space, cocycle space, and bicycle space in a special manner. This generalizes a result of Rosenstiehl and Read that characterized those planar graphs with no nonempty bicycles. © 1995 John Wiley&Sons,

ISSN:0364-9024    

DOI:10.1002/jgt.3190190209

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

年代:1995

数据来源: WILEY

摘要:

AbstractA graph is chromatically unique if it is uniquely determined by its chromatic polynomial. LetGbe a chromatically unique graph and letKmdenote the complete graph onmvertices. This paper is mainly concerned with the chromaticity ofKm+Gwhere + denotes the join of graphs. Also, it is shown that a large family of connected vertextransitive graphs that are not chromatically unique can be obtained by taking the join of some vertex‐transitive graphs. © 1995 John Wiley&Sons, I

ISSN:0364-9024    

DOI:10.1002/jgt.3190190210

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe irredundant Ramsey numbers(m, n) is the smallestpsuch that for every graphGwithpvertices, eitherGcontains ann‐element irredundant set or its complementGcontains anm‐element irredundant set. Cockayne, Hattingh, and Mynhardt have given a computer‐assisted proof thats(3, 7) = 18. The purpose of this paper is to give a self‐contained proof of this result. © 1995 John Wiley&S

ISSN:0364-9024    

DOI:10.1002/jgt.3190190211

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

年代:1995

数据来源: WILEY