共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
Zhi-Hong Chen 《Journal of Graph Theory》1993,17(1):5-21
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 G1 of order at most p without a spanning eulerian subgraph. Furthermore, we characterize the graphs that satisfy the conditions above such that G1 has order p and does not have any spanning eulerian subgraph. © 1993 John Wiley & Sons, Inc. 相似文献
3.
《Discrete Mathematics》2007,307(3-5):633-640
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. 相似文献
4.
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 相似文献
5.
For all odd integers n ≥ 1, let Gn denote the complete graph of order n, and for all even integers n ≥ 2 let Gn 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, Gn can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in Gn. © 2004 Wiley Periodicals, Inc. 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
Michele Conforti Grard Cornujols Ajai Kapoor Kristina Vukovi 《Journal of Graph Theory》1999,30(4):289-308
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 相似文献
9.
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 K4 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 相似文献
10.
Herbert Fleischner 《Journal of Graph Theory》1994,18(5):449-459
We construct 3-regular (cubic) graphs G that have a dominating cycle C such that no other cycle C1 of G satisfies V(C) ? V(C1). 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. 相似文献
11.
Van Bang Lê 《Journal of Graph Theory》1993,17(1):65-73
The concept of the line graph can be generalized as follows. The k-line graph Lk(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 Lk(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. 相似文献
12.
Let G be a (V,E) graph of order p≥2. The double vertex graph U
2
(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 相似文献
13.
David A. Pike 《Journal of Graph Theory》1995,20(4):473-479
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. 相似文献
14.
G. L. Chia 《Journal of Graph Theory》1995,19(2):251-261
A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let G be a chromatically unique graph and let Km denote the complete graph on m vertices. This paper is mainly concerned with the chromaticity of Km + 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. 相似文献
15.
Cun-Quan Zhang 《Journal of Graph Theory》1994,18(1):51-57
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 K5, then E(G) has an even circuit decomposition. 相似文献
16.
The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M1 and M2 of M(G) are adjacent if and only if |M1 − M2| = 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 相似文献
17.
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 Kn'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 相似文献
18.
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. 相似文献
19.
Kerri Morgan 《Graphs and Combinatorics》2011,27(4):547-556
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
1 with an r-clique in some graph H
2, 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. 相似文献
20.
LU Zaiping WANG Changqun & XU MingyaoLMAM School of Mathematical Sciences Peking University Beijing China Department of Mathematics Zhengzhou University Zhengzhou ChinaPresent address: Department of Mathematics Qufu Normal University Qufu China. 《中国科学A辑(英文版)》2004,47(1):1-17
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. 相似文献