共查询到20条相似文献,搜索用时 31 毫秒
1.
A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p2/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs. 相似文献
2.
Byeong Moon Kim Byung Chul Song Woonjae Hwang 《Linear algebra and its applications》2007,420(2-3):648-662
A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even. 相似文献
3.
A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with
, then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with
, then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2. 相似文献
4.
Donald W. Vanderjagt 《Discrete Mathematics》1974,10(2):391-395
A graph G is locally n-connected (locally n-edge connected) if the neighborhood of each vertex of G is n-connected (n-edge connected). The local connectivity (local edge-connectivity) of G is the maximum n for which G is locally n-connected (locally n-edge connected). It is shown that if k and m are integers with O k < m, then a graph exists which has connectivity m and local connectivity k. Furthermore, such a graph with smallest order is determined. Corresponding results are obtained involving the local connectivity and the local edge-conectivity. 相似文献
5.
Matching extension and minimum degree 总被引:1,自引:0,他引:1
Let G be a simple connected graph on 2n vertices with a perfect matching. For a given positive integer k, 1 k n − 1, G is k-extendable if for every matching M of size k in G, there exists a perfect matching in G containing all the edges of M. The problem that arises is that of characterizing k-extendable graphs. In this paper, we establish a necessary condition, in terms of minimum degree, for k-extendable graphs. Further, we determine the set of realizable values for minimum degree of k-extendable graphs. In addition, we establish some results on bipartite graphs including a sufficient condition for a bipartite graph to be k-extendable. 相似文献
6.
We answer a question of Erdös, Faudree, Reid, Schelp and Staton by showing that for every integer k 2 there is a triangle-free graph G of order n such that no degree in G is repeated more than k times and ind(G) = (1 + o(1))n/k. 相似文献
7.
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). 相似文献
8.
Yoshimi Egawa Mariko Hagita Ken-ichi Kawarabayashi Hong Wang 《Discrete Mathematics》2003,270(1-3):115-125
Let d, k and n be three integers with k3, d4k−1 and n3k. We show that if d(x)+d(y)d for each pair of nonadjacent vertices x and y of a graph G of order n, then G contains k vertex-disjoint cycles converting at least min{d,n} vertices of G. 相似文献
9.
In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γk(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γk(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices. 相似文献
10.
Artur Andrzejak 《Discrete Mathematics》1998,190(1-3):39-54
Let k be a fixed, positive integer. We give an algorithm which computes the Tutte polynomial of any graph G of treewidth at most k in time O(n2+7 log2 c), where c is twice the number of partitions of a set with 3k + 3 elements and n the number of vertices of G. 相似文献
11.
Consider a graph G and a k-uniform hypergraph
on common vertex set [n]. We say that
is G-intersecting if for every pair of edges in
there are vertices xX and yY such that x=y or x and y are joined by an edge in G. This notion was introduced by Bohman, Frieze, Ruszinkó and Thoma who proved a natural generalization of the Erd
s–Ko–Rado Theorem for G-intersecting k-uniform hypergraphs for G sparse and k=O(n1/4). In this note, we extend this result to
. 相似文献
12.
Bert Randerath Ingo Schiermeyer Meike Tewes Lutz Volkmann 《Discrete Applied Mathematics》2002,120(1-3):219-237
Let G be a graph of order n. A graph G is called pancyclic if it contains a cycle of length k for every 3kn, and it is called vertex pancyclic if every vertex is contained in a cycle of length k for every 3kn. In this paper, we shall present different sufficient conditions for graphs to be vertex pancyclic. 相似文献
13.
T. H. Pate 《Linear and Multilinear Algebra》1981,10(2):103-105
Let A be an nk × nk positive semi-definite symmetric matrix partitioned into blocks Aij each of which is an n × n matrix. In [2] Mine states a conjecture of Marcus that per(A) ≥ per(G) where G is the k × k matrix [per(Aij)]. In this paper we prove a weaker inequality namely that per(A) ≥ (k!)-1per(G). 相似文献
14.
We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k2, in which the route degree is
, the total number of routes is O(k2n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is
, the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ1 for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ1)/{f})2 for any fault f, and a routing ρ2 (using ρ1) for every n-node biconnected graph, in which the route degree is
, the total number of routes is
and D(R(G,ρ2)/{f})2 for any fault f. 相似文献
15.
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. 相似文献
16.
An L(2,1)-coloring of a graph G is a coloring of G's vertices with integers in {0,1,…,k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ(G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ(G), and the hole index ρ(G) of G is the minimum number of colors in {0,1,…,λ(G)} not used in a span coloring. We say that G is full-colorable if ρ(G)=0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span μ(G) of G as ∞ if G has no no-hole coloring; otherwise μ(G) is the minimum k for which G has a no-hole coloring using colors in {0,1,…,k}.
Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ3 are full-colorable, all graphs G with n=λ(G)+1 are full-colorable, μ(G)λ(G)+ρ(G) if G is not full-colorable and nλ(G)+2, and G has a no-hole coloring if and only if nλ(G)+1. We prove two extremal results for colorings. First, for every m1 there is a G with ρ(G)=m and μ(G)=λ(G)+m. Second, for every m2 there is a connected G with λ(G)=2m, n=λ(G)+2 and ρ(G)=m. 相似文献
17.
Tomasz
uczak 《Discrete Applied Mathematics》1991,30(2-3):213-219
It is shown that for every >0 with the probability tending to 1 as n→∞ a random graph G(n,p) contains induced cycles of all lengths k, 3 ≤ k ≤ (1 − )n log c/c, provided c(n) = (n − 1)p(n)→∞. 相似文献
18.
Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |NG(x1)NG(x2)NG(xk)|an/(a+b) for any independent subset {x1,x2,…,xk} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense. 相似文献
19.
Ludwin A.BASILIO-HERNáNDEZ Walter CARBALLOSA Jesús LEA?OS José M.SIGARRETA 《数学学报(英文版)》2019,35(3):338-354
We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial B(G; x) :=∑?(G)k=-nB_k(G) x~(n+k), where B_k(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G;x) and its coefficients.In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G. 相似文献
20.
For any natural number k, a graph G is said to be pancyclic mod k if it contains a cycle of every length modulo k. In this paper, we show that every K1,4-free graph G with minimum degree δ(G)k+3 is pancyclic mod k and every claw-free graph G with δ(G)k+1 is pancyclic mod k, which confirms Thomassen's conjecture (J. Graph Theory 7 (1983) 261–271) for claw-free graphs. 相似文献