共查询到20条相似文献,搜索用时 46 毫秒
1.
Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160
Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!]. 相似文献
2.
H. Karami S. M. Sheikholeslami Abdollah Khodkar Douglas B. West 《Graphs and Combinatorics》2012,28(1):123-131
A set S of vertices in a graph G is a connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by S is connected. The connected domination number
γ
c
(G) is the minimum size of such a set. Let d*(G)=min{d(G),d([`(G)])}{\delta^*(G)={\rm min}\{\delta(G),\delta({\overline{G}})\}} , where [`(G)]{{\overline{G}}} is the complement of G and δ(G) is the minimum vertex degree. We prove that when G and [`(G)]{{\overline{G}}} are both connected, gc(G)+gc([`(G)]) £ d*(G)+4-(gc(G)-3)(gc([`(G)])-3){{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+4-({\gamma_c}(G)-3)({\gamma_c}({\overline{G}})-3)} . As a corollary,
gc(G)+gc([`(G)]) £ \frac3n4{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \frac{3n}{4}} when δ*(G) ≥ 3 and n ≥ 14, where G has n vertices. We also prove that gc(G)+gc([`(G)]) £ d*(G)+2{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+2} when gc(G),gc([`(G)]) 3 4{{\gamma_c}(G),{\gamma_c}({\overline{G}})\ge 4} . This bound is sharp when δ*(G) = 6, and equality can only hold when δ*(G) = 6. Finally, we prove that gc(G)gc([`(G)]) £ 2n-4{{\gamma_c}(G){\gamma_c}({\overline{G}})\le 2n-4} when n ≥ 7, with equality only for paths and cycles. 相似文献
3.
Raffaele Mosca 《Graphs and Combinatorics》2001,17(3):517-528
Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ
n
:Ex≤1,x≥0}, P(C)={x∈ℜ
n
:Cx≤1,x≥0}, α
E
(G)=max{1
T
x subject to x∈P(E)}, and α
C
(G)= max{1
T
x subject to x∈P(C)}. In this paper we prove that if α
E
(G)=α
C
(G), then γ(G)=θ(G).
Received: May 20, 1998?Final version received: April 12, 1999 相似文献
4.
Let χ
t
(G) and †(G) denote respectively the total chromatic number and maximum degree of graphG. Yap, Wang and Zhang proved in 1989 that ifG is a graph of orderp having †(G)≥p−4, then χ
t
(G≤Δ(G)+2. Hilton has characterized the class of graphG of order 2n having †(G)=2n−1 such that χ
t
(G=Δ(G)+2. In this paper, we characterize the class of graphsG of order 2n having †(G)=2n−2 such that χ
t
(G=Δ(G)+2
Research supported by National Science Council of the Republic of China (NSC 79-0208-M009-15) 相似文献
5.
Futaba Okamoto Ping Zhang Varaporn Saenpholphat 《Czechoslovak Mathematical Journal》2008,58(1):271-287
For a nontrivial connected graph G of order n and a linear ordering s: v
1, v
2, …, v
n
of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t
+(G) of G is t
+(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper
traceable number of a graph. All connected graphs G for which t
+(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established.
Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand
under the grant number MRG 5080075. 相似文献
6.
. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T
i
}, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏
i
=1
n
T
i
admits an (r, d)-invariant orientation provided that d(T
1)≥d(T
2)≥4 for n=2, and d(T
1)≥5 and d(T
2)≥4 for n≥3.
Received: July 30, 1997 Final version received: April 20, 1998 相似文献
7.
Let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle, respectively, of a finite, simple graph G. Define σ4(G)=min{d(x
1)+d(x
2)+ d(x
3)+d(x
4) | {x
1,…,x
4} is independent in G}. In this paper, the difference p(G)−c(G) is considered for 2-connected graphs G with σ4(G)≥|V(G)|+3. Among others, we show that p(G)−c(G)≤2 or every longest path in G is a dominating path.
Received: August 28, 2000 Final version received: May 23, 2002 相似文献
8.
An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for
a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c¢vd(G){\chi'_{vd}(G)}. It is proved that c¢vd(G) £ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and
s2(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ
2(G) denotes the minimum degree sum of two nonadjacent vertices in G. 相似文献
9.
Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n
0(H) isolated vertices and n
1(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H{\mathcal{H}} and
d(G) 3 \fracn+m-k+n1(H)+2n0(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}}, then G contains a spanning H-subdivision with the same ground set as H{\mathcal{H}} . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that
if G is a graph of order n ≥ 3 with
d(G) 3 \fracn2{\delta(G)\ge\frac{n}{2}} , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition
d(G) 3 \fracn2{\delta(G) \ge \frac{n}{2}} then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb.
23:165–182, 2007) in a similar manner. An H-subdivision H{\mathcal{H}} in G is 1-extendible if there exists an H-subdivision H*{\mathcal{H}^{*}} with the same ground set as H{\mathcal{H}} and |H*| = |H| + 1{|\mathcal{H}^{*}| = |\mathcal{H}| + 1} . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that
d(G) 3 \fracn+m-k+n1(H)+2n0(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}} , then G is pan-H-linked. This result is sharp. 相似文献
10.
Two graphs G1 and G2 of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets do not intersect. Sauer and Spencer proved that if Δ (G1) Δ (G2) < 0.5n, then G1 and G2 pack.
In this note, we study an Ore-type analogue of the Sauer–Spencer Theorem. Let θ(G) = max{d(u) + d(v): uv∈E(G)}. We show that if θ(G1)Δ(G2) < n, then G1 and G2 pack. We also characterize the pairs (G1,G2) of n-vertex graphs satisfying θ(G1)Δ(G2) = n that do not pack.
This work was supported in part by NSF grant DMS-0400498. The work of the first author was also partly supported by grant
05-01-00816 of the Russian Foundation for Basic Research. 相似文献
12.
JieLU JinChengXIONG JianCHEN 《数学学报(英文版)》2004,20(3):415-422
Let G be a graph which contains exactly one simple closed curve. We prove that a continuous map f : G → G has zero topological entropy if and only if there exist at most k ≤ |(Edg(G) End(G) 3)/2] different odd numbers n1,...,nk such that Per(f) is contained in ∪i=1^k ∪j=0^∞ ni2^j, where Edg(G) is the number of edges of G and End(G) is the number of end points of G. 相似文献
13.
Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d
G
(u) + d
G
(v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d
G
(u) + d
G
(v) ⩾ n − 2g + 3 (resp. d
G
(u) + d
G
(v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight.
This work was supported by National Natural Science Foundation of China (Grant No. 10571013) 相似文献
14.
Inna Bumagina 《Israel Journal of Mathematics》2001,124(1):279-284
The rank of a groupG is the minimal number of elements that generateG. For any natural numbern we construct two groups,G
1 of rankr(G
1)=n andG
2 of rankr(G
2)=2n such that their amalgamated product over an infinite cyclic subgroup, malnormal in both factors, is generated by 2n=r(G
1)+r(G
2)−n elements. We also consider an example of an amalgamated product ofn factors:
such thatr(G)=n +1, andr(A)≥1. This example realizes the lower bound given by Weidmann [W1] (see Theorem 2 in the present paper). 相似文献
15.
Xiao Yun CHENG Jian Guo XIA Hou Rong QIN 《数学学报(英文版)》2007,23(5):819-826
Let K2 be the Milnor functor and let Фn (x)∈ Q[X] be the n-th cyclotomic polynomial. Let Gn(Q) denote a subset consisting of elements of the form {a, Фn(a)}, where a ∈ Q^* and {, } denotes the Steinberg symbol in K2Q. J. Browkin proved that Gn(Q) is a subgroup of K2Q if n = 1,2, 3, 4 or 6 and conjectured that Gn(Q) is not a group for any other values of n. This conjecture was confirmed for n =2^T 3S or n = p^r, where p ≥ 5 is a prime number such that h(Q(ζp)) is not divisible by p. In this paper we confirm the conjecture for some n, where n is not of the above forms, more precisely, for n = 15, 21,33, 35, 60 or 105. 相似文献
16.
Eugenia Malinnikova 《Journal of Fourier Analysis and Applications》2010,16(6):983-1006
We prove that there does not exist an orthonormal basis {b
n
} for L
2(R) such that the sequences {μ(b
n
)},
{m([^(bn)])}\{\mu(\widehat{b_{n}})\}
, and
{D(bn)D([^(bn)])}\{\Delta(b_{n})\Delta(\widehat{b_{n}})\}
are bounded. A higher dimensional version of this result that involves generalized dispersions is also obtained. The main
tool is a time-frequency localization inequality for orthonormal sequences in L
2(R
d
). On the other hand, for d>1 we construct a basis {b
n
} for L
2(R
d
) such that the sequences {μ(b
n
)},
{m([^(bn)])}\{\mu(\widehat{b_{n}})\}
, and
{D(bn)D([^(bn)])}\{\Delta(b_{n})\Delta(\widehat{b_{n}})\}
are bounded. 相似文献
17.
Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ
l
(G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ
l
(G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known
theorem of Ohba for list chromatic number, we obtain ρ
l
(G + K
n
) = ρ(G + K
n
) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ
l
(G) = ρ(G). Particularly, we determine that , where K
2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ
l
(G) = ρ(G).
Research supported by NSFC (No.10601044) and XJEDU2006S05. 相似文献
18.
Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if
G\ncong K2{G\ncong K_2}. 相似文献
19.
Claude Tardif 《Combinatorica》2005,25(5):625-632
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. 相似文献
20.
M. R. Darafsheh 《Acta Appl Math》2010,110(3):1225-1235
Let G=(V,E) be a simple connected graph with vertex set V and edge set E. The Wiener index of G is defined by W(G)=∑{x,y}⊆V
d(x,y), where d(x,y) is the length of the shortest path from x to y. The Szeged index of G is defined by Sz(G)=∑
e=uv∈E
n
u
(e|G)n
v
(e|G), where n
u
(e|G) (resp. n
v
(e|G)) is the number of vertices of G closer to u (resp. v) than v (resp. u). The Padmakar–Ivan index of G is defined by PI(G)=∑
e=uv∈E
[n
eu
(e|G)+n
ev
(e|G)], where n
eu
(e|G) (resp. n
ev
(e|G)) is the number of edges of G closer to u (resp. v) than v (resp. u). In this paper we find the above indices for various graphs using the group of automorphisms of G. This is an efficient method of finding these indices especially when the automorphism group of G has a few orbits on V or E. We also find the Wiener indices of a few graphs which frequently arise in mathematical chemistry using inductive methods. 相似文献