共查询到20条相似文献,搜索用时 140 毫秒
1.
Odile Marcotte 《Combinatorica》2001,21(3):361-394
Let G be a multigraph containing no minor isomorphic to or (where denotes without one of its edges). We show that the chromatic index of G is given by , where is the maximum valency of G and is defined as
(w(E(S)) being the number of edges in the subgraph induced by S). This result partially verifies a conjecture of Seymour [J. Combin. Theory (B) 31 (1981), pp. 82-94] and is actually a generalization
of a result proven by Seymour [Combinatorica 10 (1990), pp. 379-392] for series-parallel graphs. It is also equivalent to
the following statement: the matching polytope of a graph containing neither nor as a minor has the integer decomposition property.
Received January 10, 1997/Revised September 13, 1999
The author is also affiliated with GERAD (école des Hautes études Commerciales de Montréal). Her work was supported by Grant
OGP 0009126 from the Natural Sciences and Engineering Research Council of Canada (NSERC). 相似文献
2.
Entropy bounds for perfect matchings and Hamiltonian cycles 总被引:1,自引:1,他引:0
For a graph G = (V,E) and x: E → ℜ+ satisfying Σ
e∋υ
x
e
= 1 for each υ ∈ V, set h(x) = Σ
e
x
e
log(1/x
e
) (with log = log2). We show that for any n-vertex G, random (not necessarily uniform) perfect matching f satisfying a mild technical condition, and x
e
=Pr(e∈f),
(where H is binary entropy). This implies a similar bound for random Hamiltonian cycles.
Specializing these bounds completes a proof, begun in [6], of a quite precise determination of the numbers of perfect matchings
and Hamiltonian cycles in Dirac graphs (graphs with minimum degree at least n/2) in terms of h(G):=maxΣ
e
x
e
log(1/x
e
) (the maximum over x as above). For instance, for the number, Ψ(G), of Hamiltonian cycles in such a G, we have
.
Supported by NSF grant DMS0200856. 相似文献
3.
We investigate the induced Ramsey number
of pairs of graphs (G, H). This number is defined to be the smallest possible order of a graph Γ with the property that, whenever its edges are coloured
red and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that, for any G and H with , we have
where is the chromatic number of H and C is some universal constant. Furthermore, we also investigate imposing some conditions on G. For instance, we prove a bound that is polynomial in both k and t in the case in which G is a tree. Our methods of proof employ certain random graphs based on projective planes.
Received: October 10, 1997 相似文献
4.
On the full automorphism group of a graph 总被引:11,自引:0,他引:11
C. D. Godsil 《Combinatorica》1981,1(3):243-256
While it is easy to characterize the graphs on which a given transitive permutation groupG acts, it is very difficult to characterize the graphsX with Aut (X)=G. We prove here that for the certain transitive permutation groups a simple necessary condition is also sufficient. As a corollary
we find that, whenG is ap-group with no homomorphism ontoZ
p
wrZ
p
, almost all Cayley graphs ofG have automorphism group isomorphic toG. 相似文献
5.
In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n, we form a random graph by replacing each vertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G. The resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications
of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard
random models, and also "randomizing" given graphs. The main specific result that we prove here (Theorem 1) is that if is the smallest vertex degree in G, then almost all n-covers of G are -connected. In subsequent papers we will address other graph properties, such as girth, expansion and chromatic number.
Received June 21, 1999/Revised November 16, 2000
RID="*"
ID="*" Work supported in part by grants from the Israel Academy of Aciences and the Binational Israel-US Science Foundation. 相似文献
6.
Serguei Norine 《Combinatorica》2009,29(1):109-119
We say that a graph G is k-Pfaffian if the generating function of its perfect matchings can be expressed as a linear combination of Pfaffians of k matrices corresponding to orientations of G. We prove that 3-Pfaffian graphs are 1-Pfaffian, 5-Pfaffian graphs are 4-Pfaffian and that a graph is 4-Pfaffian if and only
if it can be drawn on the torus (possibly with crossings) so that every perfect matching intersects itself an even number
of times. We state conjectures and prove partial results for k>5.
The author was supported in part by NSF under Grant No. DMS-0200595 and DMS-0701033. 相似文献
7.
A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs. 相似文献
8.
Dezső Miklós 《Combinatorica》1992,12(3):367-369
In his thesis [3] B. D. Thatte conjectured that ifG=G
1,G
2,...G
n
is a sequence of finitely many simple connected graphs (isomorphic graphs may occur in the sequence) with the same number of vertices and edges then their shuffled edge deck uniquely determines the graph sequence (up to a permutation). In this paper we prove that there are such sequences of graphs with the same shuffled edge deck.This research was partially supported by Hungarian National Foundation of Scientific Research Grant no. 1812 相似文献
9.
Haiko Müller 《Order》1990,7(1):11-21
The investigation of alternating cycle-free matchings is motivated by the Jump-number problem for partially ordered sets and the problem of counting maximum cardinality matchings in hexagonal systems.We show that the problem of deciding whether a given chordal bipartite graph has an alternating cycle-free matching of a given cardinality is NP-complete. A weaker result, for bipartite graphs only, has been known for some time. Also, the alternating cycle-free matching problem remains NP-complete for strongly chordal split graphs of diameter 2.In contrast, we give algorithms to solve the alternating cycle-free matching problem in polynomial time for bipartite distance hereditary graphs (time O(m
2) on graphs with m edges) and distance hereditary graphs (time O(m
5)). 相似文献
10.
d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x.
We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) :
Theorem. For any d-regular graph G,
(a)
, so that ,
(b)
,
where the rates of convergence depend only on d.
Received: April 12, 1996 相似文献
11.
《Quaestiones Mathematicae》2013,36(3):401-414
AbstractA connected graph G is a cactus if any two of its cycles have at most one common vertex. Denote by the set of n-vertex cacti with matching number q. Huang, Deng and Simi? [23] identified the unique graph with the maximum spectral radius among 2q-vertex cacti with perfect matchings. In this paper, as a continuance of it, the largest and second largest spectral radii together with the corresponding graphs among are determined. Consequently, the first two largest spectral radii together with cacti having perfect matchings are also determined. 相似文献
12.
《Quaestiones Mathematicae》2013,36(4):537-548
AbstractFor a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G. 相似文献
13.
E.G. Coffman Jr. George S. Lueker Joel Spencer Peter M. Winkler 《Probability Theory and Related Fields》2001,120(4):585-599
A random rectangle is the product of two independent random intervals, each being the interval between two random points
drawn independently and uniformly from [0,1]. We prove that te number C
n
of items in a maximum cardinality disjoint subset of n random rectangles satisfies
where K is an absolute constant. Although tight bounds for the problem generalized to d > 2 dimensions remain an open problem, we are able to show that, for some absolute constat K,
Finally, for a certain distribution of random cubes we show that for some absolute constant K, the number Q
n
of items in a maximum cardinality disjoint subset of the cubes satisies
Received: 1 September 1999 / Revised version: 3 November 2000 / Published online: 14 June 2001 相似文献
14.
Maximal Energy Bipartite Graphs 总被引:1,自引:0,他引:1
Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then
must hold, characterize those bipartite graphs for which this bound is sharp, and provide an infinite family of maximal energy
bipartite graphs.
Received: December 1, 2000 Final version received: August 28, 2001
RID="*"
ID="*" The author thanks the Swedish Natural Science Research Council (NFR) – grant M12342-300 – for its support.
Acknowledgments. The authors would like to thank Ivan Gutman for encouraging them to write this paper, and for helpful discussions on this
topic. They also would like to thank Edwin van Dam for his reference concerning connected bipartite regular graphs with four
eigenvalues. 相似文献
15.
The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four. 相似文献
16.
Milan Nath 《Linear algebra and its applications》2007,427(1):42-54
For acyclic and unicyclic graphs we determine a necessary and sufficient condition for a graph G to be singular. Further, it is shown that this characterization can be used to construct a basis for the null-space of G. 相似文献
17.
Tomislav Došli? 《Discrete Mathematics》2008,308(11):2297-2300
The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least ⌈(n+1)!/4[q-p-(n-1)(2Δ-3)+4]⌉ different perfect matchings, where Δ is the maximum degree of a vertex in G. 相似文献
18.
《Quaestiones Mathematicae》2013,36(4):521-525
Abstract In 1952 Dirac introduced the Dirac type condition and proved that if G is a connected graph of order n ≥ 3 such that δ(G) ≥ n/2, then G is Hamiltonian. In this paper we consider Hamiltonian-connectedness, which extends the Hamiltonian graphs and prove that if G is a connected graph of order n ≥ 3 such that δ(G) ≥ (n ?1)/2, then G is Hamiltonian-connected or G belongs to five families of well-structured graphs. Thus, the condition and the result generalize the above condition and results of Dirac, respectively. 相似文献
19.
A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005 相似文献
20.
Some properties of the spectrum of graphs 总被引:3,自引:0,他引:3
ChangAn 《高校应用数学学报(英文版)》1999,14(1):103-107
Let G be a graph and denote by Q(G)=D(G) A(G),L(G)=D(G)-A(G) the sum and the difference between the diagonal matrix of vertex degrees and the adjacency matrix of G,respectively. In this paper,some properties of the matrix Q(G)are studied. At the same time,anecessary and sufficient condition for the equality of the spectrum of Q(G) and L(G) is given. 相似文献