共查询到20条相似文献,搜索用时 15 毫秒
1.
Sizhong Zhou 《Comptes Rendus Mathematique》2009,347(21-22):1223-1226
2.
A non-empty -regular graph on vertices is called a Deza graph if there exist constants and such that any pair of distinct vertices of has either or common neighbours. The quantities , , , and are called the parameters of and are written as the quadruple . If a Deza graph has diameter 2 and is not strongly regular, then it is called a strictly Deza graph. In the present paper, we investigate strictly Deza graphs whose parameters satisfy the conditions and . 相似文献
3.
《Discrete Mathematics》2021,344(12):112604
A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index of G is Δ or . A graph G is class 1 if , and class 2 if ; G is Δ-critical if it is connected, class 2 and for every . A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, for every . Such graphs have intimate relation to -co-critical graphs, where a non-complete graph G is -co-critical if there exists a k-coloring of such that G does not contain a monochromatic copy of but every k-coloring of contains a monochromatic copy of for every . We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all -co-critical graphs. We prove that if G is a -co-critical graph on vertices, then where ε is the remainder of when divided by 2. This bound is best possible for all and . 相似文献
4.
Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let mk(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{mk(G): GTn,k}, where Tn,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k). 相似文献
5.
Let a,b,k,r be nonnegative integers with 1≤a≤b and r≥2.LetG be a graph of order n with n(a+b)(r(a+b)-2)+ak/a.In this paper,we first show a characterization for all fractional(a,b,k)-critical graphs.Then using the result,we prove that G is all fractional(a,b,k)-critical if δ(G)≥(r-1)b2/a+k and |NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b for any independent subset {x1,x2,...,xr} in G.Furthermore,it is shown that the lower bound on the condition|NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b is best possible in some sense,and it is an extension of Lu's previous result. 相似文献
6.
7.
C. A. Barefoot L. H. Clark R. C. Entringer T. D. Porter L. A. Sz kely Zs. Tuza 《Discrete Mathematics》1996,150(1-3):31-48
A graph G is called Ck-saturated if G contains no cycles of length k but does contain such a cycle after the addition of any new edge. Bounds are obtained for the minimum number of edges in Ck-saturated graphs for all k ≠ 8 or 10 and n sufficiently large. In general, it is shown that the minimum is between n + c1n/k and n + c2n/k for some positive constants c1 and C2. Our results provide an asymptotic solution to a 15-year-old problem of Bollobás. 相似文献
8.
9.
10.
11.
Matthias Kriesell 《Journal of Graph Theory》2001,36(1):35-51
A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K2k + 2 − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001 相似文献
12.
Zhibo Chen 《Czechoslovak Mathematical Journal》2010,60(3):669-674
As introduced by F.Harary in 1994, a graph G is said to be an integral sum graph if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some vertex w in G. 相似文献
13.
A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination vertex removal stable if the removal of an arbitrary vertex leaves the total domination number unchanged. On the other hand, a graph is total domination vertex removal changing if the removal of an arbitrary vertex changes the total domination number. In this paper, we study total domination vertex removal changing and stable graphs. 相似文献
14.
15.
16.
Peter Mihók 《Discrete Mathematics》1981,37(1):123-126
For k?0, ?k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?k(G–e)<?k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order. 相似文献
17.
18.
Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers
2 ≤ s < t let f
s,t
(n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K
s
}}, where the minimum is taken over all K
t
-free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds
is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n
1/2+o(1)) ≤ f
s,s+1(n) ≤ O(n
1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f
s,s+1(n) ≤ O(n
2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n
1/2−ɛ
) ≤ f
s,s+k
(n) ≤ O(n
1/2+ɛ
. In addition, we also discuss some connections between the function f
s,t
and vertex Folkman numbers. 相似文献
20.