首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
A weighting w of the edges of a graph G induces a colouring of the vertices of G where the colour of vertex v, denoted cv, is . We show that the edges of every graph that does not contain a component isomorphic to K2 can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring of G, for every edge (u,v) of G, cucv.  相似文献   

2.
Graph Connectivity After Path Removal   总被引:1,自引:0,他引:1  
Let G be a graph and u, v be two distinct vertices of G. A u—v path P is called nonseparating if G—V(P) is connected. The purpose of this paper is to study the number of nonseparating u—v path for two arbitrary vertices u and v of a given graph. For a positive integer k, we will show that there is a minimum integer (k) so that if G is an (k)-connected graph and u and v are two arbitrary vertices in G, then there exist k vertex disjoint paths P 1[u,v], P 2[u,v], . . ., P k [u,v], such that G—V (P i [u,v]) is connected for every i (i = 1, 2, ..., k). In fact, we will prove that (k) 22k+2. It is known that (1) = 3.. A result of Tutte showed that (2) = 3. We show that (3) = 6. In addition, we prove that if G is a 5-connected graph, then for every pair of vertices u and v there exists a path P[u, v] such that G—V(P[u, v]) is 2-connected.* Supported by NSF grant No. DMS-0070059 Supported by ONR grant N00014-97-1-0499 Supported by NSF grant No. 9531824  相似文献   

3.
  The so-called Kelly conjecture states that every regular tournament on 2k+1 vertices has a decomposition into k-arc-disjoint hamiltonian cycles. In this paper we formulate a generalization of that conjecture, namely we conjecture that every k-arc-strong tournament contains k arc-disjoint spanning strong subdigraphs. We prove several results which support the conjecture:If D = (V, A) is a 2-arc-strong semicomplete digraph then it contains 2 arc-disjoint spanning strong subdigraphs except for one digraph on 4 vertices.Every tournament which has a non-trivial cut (both sides containing at least 2 vertices) with precisely k arcs in one direction contains k arc-disjoint spanning strong subdigraphs. In fact this result holds even for semicomplete digraphs with one exception on 4 vertices.Every k-arc-strong tournament with minimum in- and out-degree at least 37k contains k arc-disjoint spanning subdigraphs H 1, H 2, . . . , H k such that each H i is strongly connected.The last result implies that if T is a 74k-arc-strong tournament with speci.ed not necessarily distinct vertices u 1, u 2, . . . , u k , v 1, v 2, . . . , v k then T contains 2k arc-disjoint branchings where is an in-branching rooted at the vertex u i and is an out-branching rooted at the vertex v i , i=1,2, . . . , k. This solves a conjecture of Bang-Jensen and Gutin [3].We also discuss related problems and conjectures.
Anders YeoEmail:
  相似文献   

4.
In this paper we study sequential dynamical systems (SDS) over words. An SDS is a triple consisting of: (a) a graph Y with vertex set {v1, ..., vn}, (b) a family of Y-local functions , where K is a finite field and (c) a word w, i.e., a family (w1, ..., wk), where wi is a Y-vertex. A map is called Y-local if and only if it fixes all variables and depends exclusively on the variables , for . An SDS induces an SDS- map, , obtained by the map-composition of the functions according to w. We show that an SDS induces in addition the graph G(w,Y) having vertex set {1, ..., k} where r, s are adjacent if and only if ws, wr are adjacent in Y. G(w, Y) is acted upon by Sk via and Fix(w) is the group of G(w, Y) graph automorphisms which fix w. We analyze G(w, Y)-automorphisms via an exact sequence involving the normalizer of Fix(w) in Aut(G(w, Y)), Fix(w) and Aut(Y). Furthermore we introduce an equivalence relation over words and prove a bijection between word equivalence classes and certain orbits of acyclic orientations of G(w, Y). Received September 12, 2004  相似文献   

5.
For a vertex set {u 1,u 2,...,u k} of a graphG withn vertices, let $$\begin{gathered} s(G;\{ u_1 ,u_2 ,...,u_k \} ) = \sum {1 \leqslant i< j \leqslant k\left| {N(u_i ) \cup N(u_j )} \right|,} \hfill \\ NC_k = \min \{ s(G;\{ x_1 ,...,x_k \} )\} :\{ x_1 ,...,x_k \} is an independent set\} . \hfill \\ \end{gathered} $$ In this paper, we shall prove that ifG is 3-connected andNC 4≥3n, thenG is either a hamiltonian or Petersen graph. This generalizes some results on the neighborhood union conditions for hamiltonian graphs.  相似文献   

6.
The celebrated Erd?s, Faber and Lovász Conjecture may be stated as follows: Any linear hypergraph on ν points has chromatic index at most ν. We show that the conjecture is equivalent to the following assumption: For any graph , where ν(G) denotes the linear intersection number and χ(G) denotes the chromatic number of G. As we will see for any graph G = (V, E), where denotes the complement of G. Hence, at least G or fulfills the conjecture.   相似文献   

7.
Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on nl vertices is [l, n]-pan-connected if for any , and any integer m with lmn, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC 2(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC 2(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC 2(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.   相似文献   

8.
For a graphG, let 3 = min{ i=1 3 d(ui): {u1, u2, u3} is an independent set ofG} and = min{ i=1 3 d(ui) – is an independent set ofG}. In this paper, we shall prove the following result: LetG be a 1-tough graph withn vertices such that 3 n and – 4. ThenG is hamiltonian. This generalizes a result of Fassbender [2], a result of Flandrin, Jung and Li [3] and a result of Jung [5].Supported in part by das promotionsstipendium nach dem NaFöG and the Post-Doctoral Foundation of China.  相似文献   

9.
For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).  相似文献   

10.
A hamiltonian cycle C of a graph G is an ordered set u1,u2,…,un(G),u1 of vertices such that uiuj for ij and ui is adjacent to ui+1 for every i{1,2,…,n(G)−1} and un(G) is adjacent to u1, where n(G) is the order of G. The vertex u1 is the starting vertex and ui is the ith vertex of C. Two hamiltonian cycles C1=u1,u2,…,un(G),u1 and C2=v1,v2,…,vn(G),v1 of G are independent if u1=v1 and uivi for every i{2,3,…,n(G)}. A set of hamiltonian cycles {C1,C2,…,Ck} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u.In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs Pn and the n-dimensional star graphs Sn. It is proven that IHC(P3)=1, IHC(Pn)=n−1 if n≥4, IHC(Sn)=n−2 if n{3,4} and IHC(Sn)=n−1 if n≥5.  相似文献   

11.
Let be the 2k-uniform hypergraph obtained by letting P1, . . .,Pr be pairwise disjoint sets of size k and taking as edges all sets PiPj with ij. This can be thought of as the ‘k-expansion’ of the complete graph Kr: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V2 and taking as edges all sets of size 2k that intersect each of V1 and V2 in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2p+1. In this paper we also show that when r=2p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.  相似文献   

12.
Imagine a graph as representing a fixture list with vertices corresponding to teams, and the number of edges joiningu andv as representing the number of games in whichu andv have to play each other. Each game ends in a win, loss, or tie and we say a vector =(w 1,...,w n) is awin vector if it represents the possible outcomes of the games, withw i denoting the total number of games won by teami. We study combinatorial and geometric properties of the set of win vectors and, in particular, we consider the problem of counting them. We construct a fully polynomial randomized approximation scheme for their number in dense graphs. To do this we prove that the convex hull of the set of win vectors ofG forms an integral polymatroid and then use volume approximation techniques. Supported by the “DAAD Doktorandenstipendium des zweiten Hochschulsonderprogrammes HSPII/AUFE”. Partially supported by RAND-REC EC US030.  相似文献   

13.
The main purpose of this paper is to introduce several measures determined by a given finite directed graph. To construct σ-algebras for those measures, we consider several algebraic structures induced by G; (i) the free semigroupoid of the shadowed graph (ii) the graph groupoid of G, (iii) the disgram set and (iv) the reduced diagram set . The graph measures determined by (i) is the energy measure measuing how much energy we spent when we have some movements on G. The graph measures determined by (iii) is the diagram measure measuring how long we moved consequently from the starting positions (which are vertices) of some movements on G. The graph measures and determined by (ii) and (iv) are the (graph) groupoid measure and the (quotient-)groupoid measure, respectively. We show that above graph measurings are invariants on shadowed graphs of finite directed graphs. Also, we will consider the reduced diagram measure theory on graphs. In the final chapter, we will show that if two finite directed graphs G 1 and G 2 are graph-isomorphic, then the von Neumann algebras L (μ 1) and L (μ 2) are *-isomorphic, where μ 1 and μ 2 are the same kind of our graph measures of G 1 and G 2, respectively. Received: December 7, 2006. Revised: August 3, 2007. Accepted: August 18, 2007.  相似文献   

14.
Let n be an integer and A0,..., Ak random subsets of {1,..., n} of fixed sizes a0,..., ak, respectively chosen independently and uniformly. We provide an explicit and easily computable total variation bound between the distance from the random variable , the size of the intersection of the random sets, to a Poisson random variable Z with intensity λ = EW. In particular, the bound tends to zero when λ converges and for all j = 0,..., k, showing that W has an asymptotic Poisson distribution in this regime. Received February 24, 2005  相似文献   

15.
We prove that the identity
holds for all directed graphs G and H. Similar bounds for the usual chromatic number seem to be much harder to obtain: It is still not known whether there exists a number n such that χ(G×H) ≥ 4 for all directed graphs G, H with χ(G) ≥ χ(H) ≥ n. In fact, we prove that for every integer n ≥ 4, there exist directed graphs Gn, Hn such that χ(Gn) = n, χ(Hn) = 4 and χ(Gn×Hn) = 3.  相似文献   

16.
Matching Polynomials And Duality   总被引:2,自引:0,他引:2  
Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by and the signless matching polynomial of G by .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions and are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.  相似文献   

17.
A k-cube (or “a unit cube in k dimensions”) is defined as the Cartesian product where R i (for 1 ≤ i ≤ k) is an interval of the form [a i , a i  + 1] on the real line. The k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that the k-cubes corresponding to two vertices in G have a non-empty intersection if and only if the vertices are adjacent. The cubicity of a graph G, denoted as cub(G), is defined as the minimum dimension k such that G has a k-cube representation. An interval graph is a graph that can be represented as the intersection of intervals on the real line - i.e., the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. We show that for any interval graph G with maximum degree Δ, . This upper bound is shown to be tight up to an additive constant of 4 by demonstrating interval graphs for which cubicity is equal to .  相似文献   

18.
Ifμ is a positive measure, andA 2, ...,A n are measurable sets, the sequencesS 0, ...,S n andP [0], ...,P [n] are related by the inclusion-exclusion equalities. Inequalities among theS i are based on the obviousP [k]≧0. Letting =the average average measure of the intersection ofk of the setsA i , it is shown that (−1) k Δ k M i ≧0 fori+kn. The casek=1 yields Fréchet’s inequalities, andk=2 yields Gumbel’s and K. L. Chung’s inequalities. Generalizations are given involvingk-th order divided differences. Using convexity arguments, it is shown that forS 0=1, whenS 1N−1, and for 1≦k<Nn andv=0, 1, .... Asymptotic results asn → ∞ are obtained. In particular it is shown that for fixedN, for all sequencesM 0, ...,M n of sufficiently large length if and only if for 0<t<1.  相似文献   

19.
We examine finite words over an alphabet of pairs of letters, where each word w1w2 ... wt is identified with its reverse complement where ( ). We seek the smallest k such that every word of length n, composed from Γ, is uniquely determined by the set of its subwords of length up to k. Our almost sharp result (k~ 2n = 3) is an analogue of a classical result for “normal” words. This problem has its roots in bioinformatics. Received October 19, 2005  相似文献   

20.
On the ascending star subgraph decomposition of star forests   总被引:3,自引:0,他引:3  
LetG be a graph of size for some integern2. ThenG is said to have an ascending star subgraph decomposition ifG can be decomposed inton subgraphsG 1,G 2, ...,G n such that eachG i is a star of sizei with 1in. We shall prove in this paper that a star forest with size , possesses an ascending star subgraph decomposition if the size of each component is at leastn, which is stronger than the conjecture proposed by Y. Alavi, A. J. Boals, G. Chartrand, P. Erds and O. R. Oellermann.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号