首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M2(G)/mM1(G)/n, where M1 and M2 are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that mn=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M2/(m−1)>M1/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.  相似文献   

2.
Given three positive integers r,m and g, one interesting question is the following: What is the minimum number of vertices that a graph with prescribed degree set {r,m}, 2≤r<m, and girth g can have? Such a graph is called a bi-regular cage or an ({r,m};g)-cage, and its minimum order is denoted by n({r,m};g). In this paper we provide new upper bounds on n({r,m};g) for some related values of r and m. Moreover, if r−1 is a prime power, we construct the following bi-regular cages: ({r,k(r−1)};g)-cages for g∈{5,7,11} and k≥2 even; and ({r,kr};6)-cages for k≥2 any integer. The latter cages are of order n({r,kr};6)=2(kr2kr+1). Then this result supports the conjecture that n({r,m};6)=2(rmm+1) for any r<m, posed by Yuansheng and Liang [Y. Yuansheng, W. Liang, The minimum number of vertices with girth 6 and degree set D={r,m}, Discrete Math. 269 (2003) 249-258]. We finalize giving the exact value n({3,3k};8), for k≥2.  相似文献   

3.
The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. In a paper [G. Caporossi, D. Cvetkovi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996] Caporossi et al. conjectured that among all connected graphs G with n≥6 vertices and n−1≤m≤2(n−2) edges, the graphs with minimum energy are the star Sn with mn+1 additional edges all connected to the same vertices for mn+⌊(n−7)/2⌋, and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. The conjecture is proved to be true for m=n−1,2(n−2) in the same paper by Caporossi et al. themselves, and for m=n by Hou in [Y. Hou, Unicyclic graphs with minimal energy, J. Math. Chem. 29 (2001) 163-168]. In this paper, we give a complete solution for the second part of the conjecture on bipartite graphs. Moreover, we determine the graph with the second-minimal energy in all connected bipartite graphs with n vertices and edges.  相似文献   

4.
For integers n≥4 and νn+1, let ex(ν;{C3,…,Cn}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C3,…,Cn}-free graphs with order ν and size ex(ν;{C3,…,Cn}) are called extremal graphs and denoted by EX(ν;{C3,…,Cn}). We prove that given an integer k≥0, for each n≥2log2(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν0(r,g);{C3,…,Cg−1}).  相似文献   

5.
Let G be a 4-connected planar graph on n vertices. Malkevitch conjectured that if G contains a cycle of length 4, then G contains a cycle of length k for every k∈{n,n−1,…,3}. This conjecture is true for every k∈{n,n−1,…,n−6} with k≥3. In this paper, we prove that G also has a cycle of length n−7 provided n≥10.  相似文献   

6.
For given graphs G1,G2,…,Gk, k≥2, the multicolor Ramsey number, denoted by R(G1,G2,…,Gk), is the smallest integer n such that if we arbitrarily color the edges of a complete graph on n vertices with k colors, there is always a monochromatic copy of Gi colored with i, for some 1≤ik. Let Pk (resp. Ck) be the path (resp. cycle) on k vertices. In the paper we consider the value for numbers of type R(Pi,Pk,Cm) for odd m, km≥3 and when i is odd, and when i is even. In addition, we provide the exact values for Ramsey numbers R(P3,Pk,C4) for all integers k≥3.  相似文献   

7.
The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size mn−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P4, contains a vertex z of degree n−1 such that Gz has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and nk+3 then the extremal graph is unique and it is isomorphic to K1+(K1,k+1∪(nk−3)K1).  相似文献   

8.
A sequence m1m2≥?≥mk of k positive integers isn-realizable if there is a partition X1,X2,…,Xk of the integer interval [1,n] such that the sum of the elements in Xi is mi for each i=1,2,…,k. We consider the modular version of the problem and, by using the polynomial method by Alon (1999) [2], we prove that all sequences in Z/pZ of length k≤(p−1)/2 are realizable for any prime p≥3. The bound on k is best possible. An extension of this result is applied to give two results of p-realizable sequences in the integers. The first one is an extension, for n a prime, of the best known sufficient condition for n-realizability. The second one shows that, for n≥(4k)3, an n-feasible sequence of length k isn-realizable if and only if it does not contain forbidden subsequences of elements smaller than n, a natural obstruction forn-realizability.  相似文献   

9.
We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δk−1(H) be the largest integer d such that every (k−1)-element set of vertices of H belongs to at least d edges of H.In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k?3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)?t contains a perfect matching.For large n divisible by k, we completely determine the values of t(k,n), which turn out to be very close to n/2−k. For example, if k is odd and n is large and even, then t(k,n)=n/2−k+2. In contrast, for n not divisible by k, we show that t(k,n)∼n/k.In the proofs we employ a newly developed “absorbing” technique, which has a potential to be applicable in a more general context of establishing existence of spanning subgraphs of graphs and hypergraphs.  相似文献   

10.
For n≥3, let Ωn be the set of line segments between the vertices of a convex n-gon. For j≥2, a j-crossing is a set of j line segments pairwise intersecting in the relative interior of the n-gon. For k≥1, let Δn,k be the simplicial complex of (type-A) generalized triangulations, i.e. the simplicial complex of subsets of Ωn not containing any (k+1)-crossing.The complex Δn,k has been the central object of many papers. Here we continue this work by considering the complex of type-B generalized triangulations. For this we identify line segments in Ω2n which can be transformed into each other by a 180°-rotation of the 2n-gon. Let Fn be the set Ω2n after identification, then the complex Dn,k of type-B generalized triangulations is the simplicial complex of subsets of Fn not containing any (k+1)-crossing in the above sense. For k=1, we have that Dn,1 is the simplicial complex of type-B triangulations of the 2n-gon as defined in [R. Simion, A type-B associahedron, Adv. Appl. Math. 30 (2003) 2-25] and decomposes into a join of an (n−1)-simplex and the boundary of the n-dimensional cyclohedron. We demonstrate that Dn,k is a pure, k(nk)−1+kn dimensional complex that decomposes into a kn−1-simplex and a k(nk)−1 dimensional homology-sphere. For k=n−2 we show that this homology-sphere is in fact the boundary of a cyclic polytope. We provide a lower and an upper bound for the number of maximal faces of Dn,k.On the algebraical side we give a term order on the monomials in the variables Xij,1≤i,jn, such that the corresponding initial ideal of the determinantal ideal generated by the (k+1) times (k+1) minors of the generic n×n matrix contains the Stanley-Reisner ideal of Dn,k. We show that the minors form a Gröbner-Basis whenever k∈{1,n−2,n−1} thereby proving the equality of both ideals and the unimodality of the h-vector of the determinantal ideal in these cases. We conjecture this result to be true for all values of k<n.  相似文献   

11.
Zhiquan Hu  Hao Li 《Discrete Mathematics》2009,309(5):1020-1024
For a graph G, let σ2(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ2(G)=). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ2(G)≥n and let F be a matching of size k in G such that GF is 2-connected. Then GF is hamiltonian or GK2+(K2Kn−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ2(G)≥n and let F be a set of k edges of G such that GF is hamiltonian. Then GF is either pancyclic or bipartite. Examples show that first result is the best possible.  相似文献   

12.
For a k-graph F, let t l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K m k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K m k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and ,
. Also, we present various bounds in another special but interesting case: t 2(n, m, K 43) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K 43, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.  相似文献   

13.
The following theorem is proved: Suppose that H = (X; E1, E2, …, Em) is a hypergraph without odd cycles with n vertices and p components, such that any two edges have at most k vertices in common. If for any cycle C in H, there exist two vertices of C contained in at least two common edges of H, then Σi=1m (|Ei| ? k) ≤ n ? pk.  相似文献   

14.
Y. Caro 《Discrete Mathematics》2010,310(4):742-747
For a graph G, denote by fk(G) the smallest number of vertices that must be deleted from G so that the remaining induced subgraph has its maximum degree shared by at least k vertices. It is not difficult to prove that there are graphs for which already , where n is the number of vertices of G. It is conjectured that for every fixed k. We prove this for k=2,3. While the proof for the case k=2 is easy, already the proof for the case k=3 is considerably more difficult. The case k=4 remains open.A related parameter, sk(G), denotes the maximum integer m so that there are k vertex-disjoint subgraphs of G, each with m vertices, and with the same maximum degree. We prove that for every fixed k, sk(G)≥n/ko(n). The proof relies on probabilistic arguments.  相似文献   

15.
Given integers k,s,t with 0≤st and k≥0, a (k,t,s)-linear forest F is a graph that is the vertex disjoint union of t paths with a total of k edges and with s of the paths being single vertices. If the number of single vertex paths is not critical, the forest F will simply be called a (k,t)-linear forest. A graph G of order nk+t is (k,t)-hamiltonian if for any (k,t)-linear forest F there is a hamiltonian cycle containing F. More generally, given integers m and n with k+tmn, a graph G of order n is (k,t,s,m)-pancyclic if for any (k,t,s)-linear forest F and for each integer r with mrn, there is a cycle of length r containing the linear forest F. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply that a graph is (k,t,s,m)-pancyclic (or just (k,t,m)-pancyclic) are proved.  相似文献   

16.
Euler's well-known nonlinear relation for Bernoulli numbers, which can be written in symbolic notation as n(B0+B0)=−nBn−1−(n−1)Bn, is extended to n(Bk1+?+Bkm) for m?2 and arbitrary fixed integers k1,…,km?0. In the general case we prove an existence theorem for Euler-type formulas, and for m=3 we obtain explicit expressions. This extends the authors' previous work for m=2.  相似文献   

17.
Small k-regular graphs of girth g where g=6,8,12 are obtained as subgraphs of minimal cages. More precisely, we obtain (k,6)-graphs on 2(kq−1) vertices, (k,8)-graphs on 2k(q2−1) vertices and (k,12)-graphs on 2kq2(q2−1), where q is a prime power and k is a positive integer such that qk≥3. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth g=6,8,12.  相似文献   

18.
A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every FE(G) with |F|=k, GF is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either GKk+2,k+2, or k=4r−2 for some integer r≥3 and GC5[N2r], where N2r is the empty graph on 2r vertices and C5[N2r] is the graph obtained from C5 by replacing each vertex with a graph isomorphic to N2r.  相似文献   

19.
Let G be a graph of order n and k a positive integer. A set of subgraphs H={H1,H2,…,Hk} is called a k-degenerated cycle partition (abbreviated to k-DCP) of G if H1,…,Hk are vertex disjoint subgraphs of G such that and for all i, 1≤ik, Hi is a cycle or K1 or K2. If, in addition, for all i, 1≤ik, Hi is a cycle or K1, then H is called a k-weak cycle partition (abbreviated to k-WCP) of G. It has been shown by Enomoto and Li that if |G|=nk and if the degree sum of any pair of nonadjacent vertices is at least nk+1, then G has a k-DCP, except GC5 and k=2. We prove that if G is a graph of order nk+12 that has a k-DCP and if the degree sum of any pair of nonadjacent vertices is at least , then either G has a k-WCP or k=2 and G is a subgraph of K2Kn−2∪{e}, where e is an edge connecting V(K2) and V(Kn−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}.  相似文献   

20.
A digraph D is strong if it contains a directed path from x to y for every choice of vertices x,y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer kn−2 so that D contains a spanning strong subdigraph with at most 2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)nc) algorithm for deciding whether a given strong digraph D on n vertices contains a spanning strong subdigraph with at most 2n−2−k arcs.We furthermore prove that if k≥1 and D has no cut vertex then it has a kernel of order at most (2k−1)2. We finally discuss related problems and conjectures.  相似文献   

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

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