共查询到20条相似文献,搜索用时 0 毫秒
1.
We construct highly edge-connected -regular graphs of even order which do not contain pairwise disjoint perfect matchings. When is a multiple of 4, the result solves a problem of Thomassen [4]. 相似文献
2.
3.
4.
5.
Angelika Hellwig 《Discrete Mathematics》2008,308(15):3265-3296
Let D be a graph or a digraph. If δ(D) is the minimum degree, λ(D) the edge-connectivity and κ(D) the vertex-connectivity, then κ(D)?λ(D)?δ(D) is a well-known basic relationship between these parameters. The graph or digraph D is called maximally edge-connected if λ(D)=δ(D) and maximally vertex-connected if κ(D)=δ(D). In this survey we mainly present sufficient conditions for graphs and digraphs to be maximally edge-connected as well as maximally vertex-connected. We also discuss the concept of conditional or restricted edge-connectivity and vertex-connectivity, respectively. 相似文献
6.
《Journal of Graph Theory》2018,87(3):356-361
We investigate the minimum order of a linear r‐regular k‐uniform hypergraph, also known as an ‐combinatorial configuration, which contains a given linear k‐uniform hypergraph of maximum (vertex) degree at most r. 相似文献
7.
Svante Janson 《Random Structures and Algorithms》2020,56(4):1070-1116
We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph. 相似文献
8.
9.
Letk⩾2 be an integer and let G be a graph of ordern with minimum degree at leastk, n⩾8k -16 for evenn and n⩾6k - 13 for oddn. If the degree sum of each pair of nonadjacent vertices of G is at least n, then for any given Hamiltonian cycleC. G has a [k, k + 1]-factor containingC
Preject supported partially by an exchange program between the Chinese Academy of Sciences and the Japan Society for Promotion
of Sciences and by the National Natural Science Foundation of China (Grant No. 19136012) 相似文献
10.
In this paper, we study the algebraic connectivity of a Hamiltonian graph, and determine all Hamiltonian graphs whose algebraic connectivity attain the minimum among all Hamiltonian graphs on n vertices. 相似文献
11.
王骁力 《数学物理学报(A辑)》2004,24(4):475-479
该文证明若G是2n阶均衡二分图,δ(G)≥(2n-1)/3,则对任何正整数k,n≥4k时,任给G的一个完美对集M,G中存在一个包含M的所有边的恰含k个分支的2 因子(k=1,n=5且δ(G)=3除外). 特别k=2时,在条件n≥5且δ(G)≥(n+2)/2下,结论也成立. 这里所给的δ(G)的下界是最好的可能.
相似文献
12.
A graph is said to beK
1,3-free if it contains noK
1,3 as an induced subgraph. It is shown in this paper that every 2-connectedK
1,3-free graph contains a connected [2,3]-factor. We also obtain that every connectedK
1,3-free graph has a spanning tree with maximum degree at most 3.
This research is partially supported by the National Natural Sciences Foundation of China and by the Natural Sciences Foundation
of Shandong Province of China. 相似文献
13.
ON CONNECTED FACTORS IN K_(1,3)-FREE GRAPHS 总被引:1,自引:0,他引:1
1.IntroductionWeconsiderfinitesimplegraphs,andfollowBondyandMurtyl'lforgeneralterminologyandnotation.LetG=(V(G),E(G))beagraphwithavertexsetV(G)andanedgesetE(G).ForavertexvEV(G),N(v,G)denotesthesetofneighborsofvinG,anddG(v)=IN(v,G)l.Foravertexsubset(resp.subgraph)HofG,G--HdenotesthesubgraphofGobtainedfromGbydeletingthevenicesinHtogetherwiththeedgesincidelltwiththem.IfAisanedgesubsetofGandHasubgraphofG,thenH AdenotesthesubgraphofGobtainedfromHbyaddingtheedgesinAtogetherwiththeven… 相似文献
14.
A graph G is a {d, d+k}-graph, if one vertex has degree d+k and the remaining vertices of G have degree d. In the special case of k = 0, the graph G is d-regular. Let k, p ⩾ 0 and d, n ⩾ 1 be integers such that n and p are of the same parity. If G is a connected {d, d+k{-graph of order n without a matching M of size 2|M| = n − p, then we show in this paper the following: If d = 2, then k ⩾ 2(p + 2) and
If d ⩾ 3 is odd and t an integer with 1 ⩽ t ⩽ p + 2, then
If d ⩾ 4 is even, then
The special case k = p = 0 of this result was done by Wallis [6] in 1981, and the case p = 0 was proved by Caccetta and Mardiyono [2] in 1994. Examples show that the given bounds (i)–(viii) are best possible. 相似文献
(i) | n ⩾ k + p + 6. |
(ii) | n ⩾ d + k + 1 for k ⩾ d(p + 2) |
(iii) | n ⩾ d(p + 3) + 2t + 1 for d(p + 2 −t) + t ⩽ k ⩽ d(p + 3 −t) + t − 3 |
(iv) | n ⩾ d(p + 3) + 2p + 7 for k ⩽ p. |
(v) | n ⩾ d + k + 2 − η for k ⩾ d(p + 3) + p + 4 + η |
(vi) | n ⩾ d + k + p + 2 − 2t = d(p + 4) + p + 6 for k = d(p + 3) + 4 + 2t and p ⩾ 1 |
(vii) | n ⩾ d + k + p + 4 for d(p + 2) ⩽ k ⩽ d(p + 3) + 2 |
(viii) | n ⩾ d(p + 3) + p + 4 for k ⩽ d(p + 2) − 2, where 0 ⩽ t ⩽ 1/2p − 1 and η = 0 for even p and 0 ⩽ t ⩽ 1/2(p − 1) and η = 1 for odd p. |
15.
Plesnik in 1972 proved that an (m - 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and (or) excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik's result and the results obtained by Liu et al. in 1998, and improve Katerinis' result obtained 1993. Furthermore, we show that the results in this paper are the best possible. 相似文献
16.
S. Akbari M. Dalirrooyfard K. Ehsani K. Ozeki R. Sherkati 《Journal of Graph Theory》2020,93(4):483-502
Let be a graph and be a mapping. The graph is said to be - avoiding if there exists an orientation of such that for every , where denotes the out-degree of in the directed graph with respect to . In this paper it is shown that if is bipartite and for every , then is -avoiding. The bound is best possible. For every graph , we conjecture that if for every , then is -avoiding. We also argue about this conjecture for the best possibility of the conditions and also show some partial solutions. 相似文献
17.
Let G be a connected simple graph on n vertices. The Laplacian index of G, namely, the greatest Laplacian eigenvalue of G, is well known to be bounded above by n. In this paper, we give structural characterizations for graphs G with the largest Laplacian index n. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary
and sufficient condition on n and k for the existence of a k-regular graph G of order n with the largest Laplacian index n. We prove that for a graph G of order n ⩾ 3 with the largest Laplacian index n, G is Hamiltonian if G is regular or its maximum vertex degree is Δ(G) = n/2. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce
miscellaneous related results.
The first author is supported by NNSF of China (No. 10771080) and SRFDP of China (No. 20070574006).
The work was done when Z. Chen was on sabbatical in China. 相似文献
18.
This article describes the structure of the graph minimizing the algebraic connectivity among all connected graphs made with some given blocks with fixed number of pendant blocks, the blocks that have exactly one point of articulation. As an application, we conclude that over all graphs made with given blocks, the algebraic connectivity is minimum for a graph whose block structure is a path. 相似文献
19.
A. Abouelaoualim K. Ch. Das W. Fernandez de la Vega M. Karpinski Y. Manoussakis C. A. Martinhon R. Saad 《Journal of Graph Theory》2010,64(1):63-86
Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ?(n+1)/2? has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010 相似文献
20.
Alfredo García Ferran Hurtado Clemens Huemer Javier Tejel Pavel Valtr 《Computational Geometry》2009,42(9):913-922
Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph. 相似文献