On 3-Edge-Connected Supereulerian Graphs

The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995 that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d _G (u) + d _G (v) ≥ 9, then G has a spanning eulerian subgraph.     

A degree condition for spanning eulerian subgraphs

Let p ≥ 2 be a fixed integer. Let G be a simple and 2-edge-connected graph on n vertices, and let g be the girth of G. If d(u) + d(v) ≥ (2/(g ? 2))((n/p) ? 4 + g) holds whenever uv ? E(G), and if n is sufficiently large compared to p, then either G has a spanning eulerian subgraph or G can be contracted to a graph G₁ of order at most p without a spanning eulerian subgraph. Furthermore, we characterize the graphs that satisfy the conditions above such that G₁ has order p and does not have any spanning eulerian subgraph. © 1993 John Wiley & Sons, Inc.     

Series parallel extensions of plane graphs to dual-eulerian graphs

A plane graph is dual-eulerian if it has an eulerian tour with the property that the same sequence of edges also forms an eulerian tour in the dual graph. Dual-eulerian graphs are of interest in the design of CMOS VLSI circuits.Every dual-eulerian plane graph also has an eulerian Petrie (left–right) tour thus we consider series-parallel extensions of plane graphs to graphs, which have eulerian Petrie tours. We reduce several special cases of extensions to the problem of finding hamiltonian cycles. In particular, a 2-connected plane graph G has a single series parallel extension to a graph with an eulerian Petrie tour if and only if its medial graph has a hamiltonian cycle.     

(2 + ϵ)‐Coloring of planar graphs with large odd‐girth

The odd‐girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function ƒ(ϵ) for each ϵ : 0 < ϵ < 1 such that, if the odd‐girth of a planar graph G is at least ƒ(ϵ), then G is (2 + ϵ)‐colorable. Note that the function ƒ(ϵ) is independent of the graph G and ϵ → 0 if and only if ƒ(ϵ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd‐girth of planar graphs. This lemma is expected to have applications in related problems. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 109–119, 2000     

Decompositions of complete graphs into triangles and Hamilton cycles

For all odd integers n ≥ 1, let G_n denote the complete graph of order n, and for all even integers n ≥ 2 let G_n denote the complete graph of order n with the edges of a 1‐factor removed. It is shown that for all non‐negative integers h and t and all positive integers n, G_n can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in G_n. © 2004 Wiley Periodicals, Inc.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Total chromatic number of complete r-partite graphs

Rosenfeld (1971) proved that the Total Colouring Conjecture holds for balanced complete r-partite graphs. Bermond (1974) determined the exact total chromatic number of every balanced complete r-partite graph. Rosenfeld's result had been generalized recently to complete r-partite graphs by Yap (1989). The main result of this paper is to prove that the total chromatic number of every complete r-partite graph G of odd order is Δ (G) + 1. This result gives a partial generalization of Bermond's theorem.     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Hamilton weights and Petersen minors*

A (1, 2)‐eulerian weight w of a cubic graph is called a Hamilton weight if every faithful circuit cover of the graph with respect to w is a set of two Hamilton circuits. Let G be a 3‐connected cubic graph containing no Petersen minor. It is proved in this paper that G admits a Hamilton weight if and only if G can be obtained from K₄ by a series of Δ?Y‐operations. As a byproduct of the proof of the main theorem, we also prove that if G is a permutation graph and w is a (1,2)‐eulerian weight of G such that (G, w) is a critical contra pair, then the Petersen minor appears “almost everywhere” in the graph G. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 197–219, 2001     

Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs

We construct 3-regular (cubic) graphs G that have a dominating cycle C such that no other cycle C₁ of G satisfies V(C) ? V(C₁). By a similar construction we obtain loopless 4-regular graphs having precisely one hamiltonian cycle. The basis for these constructions are considerations on the uniqueness of a cycle decomposition compatible with a given eulerian trail in some eulerian graph.     

Perfect k-line graphs and k-total graphs

The concept of the line graph can be generalized as follows. The k-line graph L_k(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in L_k(G) if and only if they have in G k ? 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3-line graphs and 3-total graphs. Moreover, perfect 3-line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley & Sons, Inc.     

Survey of Double Vertex Graphs

 Let G be a (V,E) graph of order p≥2. The double vertex graph U ₂ (G) is the graph whose vertex set consists of all 2-subsets of V such that two distinct vertices {x,y} and {u,v} are adjacent if and only if |{x,y}∩{u,v}|=1 and if x=u, then y and v are adjacent in G. For this class of graphs we discuss the regularity, eulerian, hamiltonian, and bipartite properties of these graphs. A generalization of this concept is n-tuple vertex graphs, defined in a manner similar to double vertex graphs. We also review several recent results for n-tuple vertex graphs. Received: October, 2001 Final version received: September 20, 2002 Dedicated to Frank Harary on the occasion of his Eightieth Birthday and the Manila International Conference held in his honor     

Hamilton decompositions of some line graphs

The main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that if G is a bipartite (2k + 1)-regular graph that is Hamilton decomposable, then the line graph, L(G), of G is also Hamilton decomposable. A similar result is obtained for 5-regular graphs, thus providing further evidence to support Bermond's conjecture. © 1995 John Wiley & Sons, Inc.     

On the join of graphs and chromatic uniqueness

A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let G be a chromatically unique graph and let K_m denote the complete graph on m vertices. This paper is mainly concerned with the chromaticity of K_m + G where + 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, Inc.     

On even circuit decompositions of eulerian graphs

Let G be an eulerian graph without odd block. It was proved by P. D. Seymour that if G is planar, then E(G) has a circuit decomposition F such that each circuit of F is of even length. In this paper the theorem of Seymour is generalized: If G contains no subgraph contractible to K₅, then E(G) has an even circuit decomposition.     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Coloring graphs which have equibipartite complements

If G is a graph of order $2n \geq 4$ with an equibipartite complement, then G is Class 1 (i.e., the chromatic index of G is Δ (G)) if and only if G is not the union of two disjoint K_n's with n odd. Similarly if G is a graph of order 2n ≥ 6 whose complement G is equibipartite with bipartition (A, D), and if both G and B, the induced bipartite subgraph of G with bipartition (A, D), have a 1-factor, then G is Type 1 (i.e., the total chromatic number of G is Δ (G) + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 183–194, 1997     

Perfect Matchings in Total Domination Critical Graphs

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination number. A 3 _t EC graph is a total domination edge-critical graph with total domination number 3 and a 3 _t VC graph is a total domination vertex-critical graph with total domination number 3. A graph G is factor-critical if G − v has a perfect matching for every vertex v in G. In this paper, we show that every 3 _t EC graph of even order has a perfect matching, while every 3 _t EC graph of odd order with no cut-vertex is factor-critical. We also show that every 3 _t VC graph of even order that is K _1,7-free has a perfect matching, while every 3 _t VC graph of odd order that is K _1,6-free is factor-critical. We show that these results are tight in the sense that there exist 3 _t VC graphs of even order with no perfect matching that are K _1,8-free and 3 _t VC graphs of odd order that are K _1,7-free but not factor-critical.     

Pairs of Chromatically Equivalent Graphs

Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. In this paper we give the means to construct infinitely many pairs of chromatically equivalent graphs where one graph in the pair is clique-separable, that is, can be obtained by identifying an r-clique in some graph H ₁ with an r-clique in some graph H ₂, and the other graph is non-clique-separable. There are known methods for finding pairs of chromatically equivalent graphs where both graphs are clique-separable or both graphs are non-clique-separable. Although examples of pairs of chromatically equivalent graphs where only one of the graphs is clique-separable are known, a method for the construction of infinitely many such pairs was not known. Our method constructs such pairs of graphs with odd order n ≥ 9.     

On semisymmetric cubic graphs of order 6p~2

A graph r is said to be G-semisymmetric if it is regular and there exists a subgroup G of A := Aut(Г) acting transitively on its edge set but not on its vertex set. In the case of G. = A, we call r a semisymmetric graph. The aim of this paper is to investigate (G-)semisymmetric graphs of prime degree. We give a group-theoretical construction of such graphs, and give a classification of semisymmetric cubic graphs of order 6p2 for an odd prime p.