共查询到20条相似文献,搜索用时 484 毫秒
1.
We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r,n) such that every n-term graphic sequence π = (d1,d2,...,dn) with term sum σ(π) = d1 + d2 + ... + dn ≥ σ(Kr,r,n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. π has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined. 相似文献
2.
Michael Ferrara 《Graphs and Combinatorics》2007,23(3):263-269
An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = Km1∪ Km2∪...∪ Kmk when n is a sufficiently large integer. This is accomplished by determining σ(Kj + kK2,n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = ∑ mi. 相似文献
3.
A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d1, d2,⋯, d2) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP
k-graphic if it has a realizationG having propertyP
k
. The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d1, d2,…, d2) without zero terms and with degree sum σ(π)=(d
1+d
2+ …+d
2) at least σ(k,n) is potentially Pk-graphic has been proved positive.
Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation
of National Education Department of China. 相似文献
4.
Jian-Hua Yin 《Czechoslovak Mathematical Journal》2009,59(2):481-487
Let r ≥ 3, n ≥ r and π = (d
1, d
2, ..., d
n
) be a non-increasing sequence of nonnegative integers. If π has a realization G with vertex set V (G) = {v
1, v
2, ..., v
n
} such that d
G
(v
i
) = d
i
for i = 1, 2, ..., n and v
1
v
2 ... v
r
v
1 is a cycle of length r in G, then π is said to be potentially C
r
″-graphic. In this paper, we give a characterization for π to be potentially C
r
″-graphic.
This work was supported by the grant of National Natural Science Foundation of China No. 10861006 and China Scholarship Council. 相似文献
5.
The set of all non-increasing nonnegative integer sequences π = (d(v
1), d(v
2), …, d(v
n
)) is denoted by NS
n
. A sequence π ∈ NS
n
is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of π. The set of all graphic sequences in NS
n
is denoted by GS
n
. A graphical sequence π is potentially H-graphical if there is a realization of π containing H as a subgraph, while π is forcibly H-graphical if every realization of π contains H as a subgraph. Let K
k
denote a complete graph on k vertices. Let K
m
−H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of K
m
). This paper summarizes briefly some recent results on potentially K
m
−G-graphic sequences and give a useful classification for determining σ (H, n). 相似文献
6.
Meng-xiao Yin 《应用数学学报(英文版)》2006,22(3):451-456
Let a(Kr,+1 - K3,n) be the smallest even integer such that each n-term graphic sequence п= (d1,d2,…dn) with term sum σ(п) = d1 + d2 +…+ dn 〉 σ(Kr+1 -K3,n) has a realization containing Kr+1 - K3 as a subgraph, where Kr+1 -K3 is a graph obtained from a complete graph Kr+1 by deleting three edges which form a triangle. In this paper, we determine the value σ(Kr+1 - K3,n) for r ≥ 3 and n ≥ 3r+ 5. 相似文献
7.
Jian-Hua Yin 《Discrete Mathematics》2011,(21):2485
For a given graph H, a non-increasing sequence π=(d1,d2,…,dn) of nonnegative integers is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. The split graph on r+s vertices is denoted by Sr,s. In this paper, we give a Rao-type characterization for π to be potentially Sr,s-graphic. A simplification of this characterization is also presented. 相似文献
8.
An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d1,d2,…,dn) of nonnegative integers is said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for r-graphic sequences to be potentially -graphic are given. These are generalizations from 1-graphs to r-graphs of four theorems due to Rao [A.R. Rao, The clique number of a graph with given degree sequence, in: A.R. Rao (Ed.), Proc. Symposium on Graph Theory, in: I.S.I. Lecture Notes Series, vol. 4, MacMillan and Co. India Ltd., (1979), 251–267; A.R. Rao, An Erdös-Gallai type result on the clique number of a realization of a degree sequence (unpublished)] and Kézdy and Lehel [A.E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), in: Combinatorics, Graph Theory, and Algorithms, vol. 2, New Issues Press, Kalamazoo Michigan, 1999, 535–544]. 相似文献
9.
尹建华 《数学物理学报(A辑)》2009,29(5):1376-1389
设K r +1是一个r +1个顶点的完全图. 一个可图序列π =(d1, d2,…, dn)称为是蕴含K r+1 -可图的, 如果π有一个实现包含
K r +1作为子图. 该文进一步研究了蕴含K r+1 -可图序列的一些新的条件, 证明了这些条件包含文献[14,10,11]中的一些主要结果和当n≥5r/2 +1时,σ(K r+1, n)之值(此值在文献[2]中被猜测, 在文献[6,7,8,3]中被证实). 此外, 确定了所有满足n≥5, d5≥4 且不蕴含K5 -可图序列π=(d1, d2,…, dn)的集合. 相似文献
10.
The split graph K rVK s on r+s vertices is denoted by S r,s. A graphic sequence π = (d 1, d 2, ···, d n) is said to be potentially S r,s-graphic if there is a realization of π containing S r,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially S r,s-graphic is obtained, which extends an analogous condition for p to be potentially K r+1-graphic due to Yin and Li (Discrete Math. 301 (2005) 218–227). As an application of this condition, we further determine the values of σ(S r,s, n) for n ≥ 3r + 3s - 1. 相似文献
11.
Let K
m
-H be the graph obtained from K
m
by removing the edges set E(H) of H where H is a subgraph of K
m
. In this paper, we characterize the potentially K
5-P
4 and K
5-Y
4-graphic sequences where Y
4 is a tree on 5 vertices and 3 leaves.
Research was supported by NNSF of China (10271105) and by NSF of Fujian (Z0511034), Fujian Provincial Training Foundation
for “Bai-Quan-Wan Talents Engineering”, Project of Fujian Education Department, Project of Zhangzhou Teachers College and
by NSERC. 相似文献
12.
JianHua Yin 《中国科学 数学(英文版)》2010,53(11):2893-2905
Let r 3, n r and π = (d1, d2, . . . , dn) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains Cr (a cycle of length r) as a subgraph, then π is said to be potentially Cr-graphic. Li and Yin (2004) posed the following problem: characterize π = (d1, d2, . . . , dn) such that π is potentially Cr-graphic for r 3 and n r. Rao and Rao (1972) and Kundu (1973) answered this problem for the case of n = r. In this paper, this problem is solved completely. 相似文献
13.
A sequence {d
1, d
2, . . . , d
n
} of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v
1, v
2, . . . , v
n
such that the degree d(v
i
) of the vertex v
i
equals d
i
for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize
sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl
Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler,
Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow. 相似文献
14.
LetX (Δ) be the real toric variety associated to a smooth fan Δ. The main purpose of this article is: (i) to determine the fundamental
group and the universal cover ofX (Δ), (ii) to give necessary and sufficient conditions on Δ under which π1(X(Δ)) is abelian, (iii) to give necessary and sufficient conditions on Δ under whichX(Δ) is aspherical, and when Δ is complete, (iv) to give necessary and sufficient conditions forC
Δ to be aK (π, 1) space whereC
Δ is the complement of a real subspace arrangement associated to Δ. 相似文献
15.
Jian-Hua Yin 《Czechoslovak Mathematical Journal》2012,62(3):863-867
The split graph K r + $\overline {{K_s}} $ on r+s vertices is denoted by S r,s . A non-increasing sequence π = (d 1, d 2, …, d n ) of nonnegative integers is said to be potentially S r,s -graphic if there exists a realization of π containing S r,s as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for π to be potentially S r,s -graphic. They are extensions of two theorems due to A.R.Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series 4 (1979), 251–267 and An Erd?s-Gallai type result on the clique number of a realization of a degree sequence, unpublished). 相似文献
16.
Narong Punnim 《Graphs and Combinatorics》2002,18(4):781-785
Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:
where is the graph of realizations of d.
Thus the two invariants a:=min(ω,d) and b:=max(ω,d) naturally arise. For a graphic degree sequence d=r
n
:=(r,r,…,r) where r is the vertex degree and n is the number of vertices, the exact values of a and b are found in all situations. Since the independence number, α(G)=ω(Gˉ), we obtain parallel results for the independence number of graphs.
Received: October, 2001 Final version received: July 25, 2002
RID="*"
ID="*" Work supported by The Thailand Research Fund, under the grant number BRG/09/2545 相似文献
17.
Jian-Hua Yin 《Graphs and Combinatorics》2012,28(4):585-595
A graphic sequence π?=?(d 1, d 2, . . . , d n ) is said to be potentially K 1,1,s -graphic if there is a realization of π containing K 1,1,s as a subgraph, where K 1,1,s is the 1?× 1?× s complete 3-partite graph. In this paper, a simple characterization of potentially K 1,1,s -graphic sequences for s?≥ 2 and n?≥ 3s?+?1 is obtained. This characterization implies Lai’s conjecture on σ(K 1,1,s , n), which was confirmed by J.H. Yin, J.S. Li and W.Y. Li, and the values of σ(K 2,s , n) for s?≥ 4 and n?≥ 3s?+?1, where K 2,s is the 2?× s complete bipartite graph. 相似文献
18.
Let r≥ 1, k≥ 2 and Fm1 ,...,mki;r denote the most general definition of a friendship graph, that is, the graph of Kr+m1 , . . . , Kr+mk meeting in a common r set, where Kr+mi is the complete graph on r + mi vertices. Clearly, | Fm1 ,...,mki;r | = m1+ ··· + mk + r. Let σ(Fm1 ,...,mki;r , n) be the smallest even integer such that every n-term graphic sequence π = (d1, d2, . . . , dn) with term sum σ(π) = d1 + d2 + ··· + dn ≥σ(Fm1 ,...,mki;r,n) has a realization G containing Fm1 ,...,mki;r as a subgraph. In this paper, we determine σ(Fm1 ,...,mki;r,n) for n sufficiently large. 相似文献
19.
Jian-Hua Yin 《Discrete Mathematics》2008,308(24):6226-6232
Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2+?+dn≥σ(H,n) has a realization G containing H as a subgraph. Let Ft,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of Kt meeting in a common r set, where Kt is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(Ft,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large. 相似文献
20.
A nonincreasing sequence of nonnegative integers π=(d1,d2,…,dn) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and n∈Z+, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(Kj+Ks,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large. 相似文献