共查询到20条相似文献,搜索用时 31 毫秒
1.
We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding
as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K
n
)=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2]. 相似文献
2.
Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where
. If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et
al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G
i}1≤i≤a
such that G
i is σ-unreal and δ(G
i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞.
Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education
Ministry of China. 相似文献
3.
For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs.
This research was supported by NSERC grant A7213 相似文献
4.
Letcc(G) (resp. cp(G)) be the least number of complete subgraphs needed to cover (resp. partition) the edges of a graphG. We present bounds on max {cc(G)+cc(Ḡ)}, max {cp(G)+cp(Ḡ)}, max {cc(G)cc(Ḡ)} and max {cp(G)cp(Ḡ)} where the maxima are taken over all graphsG onn vertices and Ḡ is the complement ofG inK
n
. Several related open problems are also given. 相似文献
5.
Michael Stiebitz 《Combinatorica》1982,2(3):315-323
Tibor Gallai made the following conjecture. LetG be ak-chromatic colour-critical graph. LetL denote the set of those vertices ofG having valencyk−1 and letH be the rest ofV(G). Then the number of components induced byL is not less than the number of components induced byH, providedL ≠ 0.
We prove this conjecture in a slightly generalized form.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
6.
Closed Separator Sets 总被引:1,自引:0,他引:1
Matthias Kriesell 《Combinatorica》2005,25(5):575-598
A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G.
A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G.
A graph H with
is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán.
Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree. 相似文献
7.
Let G = (V (G),E(G)) be a graph with vertex set V (G) and edge set E(G), and g and f two positive integral functions from V (G) to Z+-{1} such that g(v) ≤ f(v) ≤ dG(v) for all v ∈V (G), where dG(v) is the degree of the vertex v. It is shown that every graph G, including both a [g,f]-factor and a hamiltonian path, contains a connected [g,f +1]-factor. This result also extends Kano’s conjecture concerning the existence of connected [k,k+1]-factors in graphs.
* The work of this author was supported by NSFC of China under Grant No. 10271065, No. 60373025.
† The work of these authors was also supported in part by the US Department of Energy’s Genomes to Life program (http://doegenomestolife.org/)
under project, “Carbon Sequestration in Synechococcus sp.: From Molecular Machines to Hierarchical Modeling” (www.genomes2life.org)
and by National Science Foundation (NSF/DBI-0354771,NSF/ITR-IIS-0407204). 相似文献
8.
ZhaoHaixing LiuRuying ZhangShenggui 《高校应用数学学报(英文版)》2004,19(1):116-124
For a graph G,P(G,λ)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G-H,if P(G,λ)=p(H,λ). Let[G]= {H|H-G}. If [G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(G,6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ(G)= 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these results the chromaticity of 5-partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained. 相似文献
9.
Peter Frankl 《Combinatorica》1984,4(2-3):141-148
LetX be a finite set ofn elements and ℓ a family ofk-subsets ofX. Suppose that for a given setL of non-negative integers all the pairwise intersections of members of ℓ have cardinality belonging toL. Letm(n, k, L) denote the maximum possible cardinality of ℓ. This function was investigated by many authors, but to determine its exact
value or even its correct order of magnitude appears to be hopeless. In this paper we investigate the case |L|=3. We give necessary and sufficient conditions form(n, k, L)=O(n) andm(n, k, L)≧O(n
2), and show that in some casesm(n, k, L)=O(n
3/2), which is quite surprising. 相似文献
10.
P. D. Seymour 《Combinatorica》1996,16(2):223-231
LetG be an eulerian digraph; let (G) be the maximum number of pairwise edge-disjoint directed circuits ofG, and (G) the smallest size of a set of edges that meets all directed circuits ofG. Borobia, Nutov and Penn showed that (G) need not be equal to (G). We show that (G)=(G) provided thatG has a linkless embedding in 3-space, or equivalently, if no minor ofG can be converted toK
6 by –Y andY– operations. 相似文献
11.
A. V. Kostochka 《Combinatorica》1985,5(3):229-235
Leth(G) be the largest number of edges of the graphG. no two of which are contained in the same clique. ForG without isolated vertices it is proved that ifh(G)≦5, thenχ(
)≦h(G), but ifh(G)=6 thenχ(
) can be arbitrarily large. 相似文献
12.
Ervin Győri 《Combinatorica》1981,1(3):263-273
It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev
1, ...,v
n
≠V(G) and for any sequence of positive integersk
1, ...,k
n
such thatk
1+...+k
n
=|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv
1, ...,v(n), and the class of the partition containingv
i
induces a connected subgraph consisting ofk
i
vertices, fori=1, 2, ...,n. Now fix the integersk
1, ...,k
n
. In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv
1, ...,v
n
≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG. 相似文献
13.
For a graphG let ℒ(G)=Σ{1/k contains a cycle of lengthk}. Erdős and Hajnal [1] introduced the real functionf(α)=inf {ℒ (G)|E(G)|/|V(G)|≧α} and suggested to study its properties. Obviouslyf(1)=0. We provef (k+1/k)≧(300k logk)−1 for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths. 相似文献
14.
Palanivel Manoharan 《manuscripta mathematica》2008,125(1):127-137
For a fibre preserving map ϕ: E → E on a fibration (E, π, B), we construct a grading preserving map T(ϕ, π) between H*(E) and H*(B) that generalizes the Lefschetz number. If T(ϕ, π) is an isomorphism between H
0(E) and H
0(B), then π restricts to a surjective local diffeomorphism on each connected component of the fixed point set of ϕ under a transversality condition. This yields a characterization for the bundle H → G → G/H to be trivial when π
1 (G/H) = 0. 相似文献
15.
J. M. A. M. van Neerven 《Semigroup Forum》1991,43(1):378-394
The adjoint of aC
0-semigroup on a Banach spaceX induces a locally convex σ(X,X
ℴ)-topology inX, which is weaker than the weak topology ofX. In this paper we study the relation between these two topologies. Among other things a class of subsets ofX is given on which they coincide. As an application, an Eberlein-Shmulyan type theorem is proved for the σ(X,X
ℴ)-topology and it is shown that the uniform limit of σ(X,X
ℴ)-compact operators is σ(X,X
ℴ)-compact. Finally our results are applied to the problem when the Favard class of a semigroup equals the domain of the infinitesimal
generator. 相似文献
16.
A. V. Karzanov 《Combinatorica》1985,5(4):325-335
A family ℱ of cuts of an undirected graphG=(V, E) is known to have the weak MFMC-property if (i) ℱ is the set ofT-cuts for someT⊆V with |T| even, or (ii) ℱ is the set of two-commodity cuts ofG, i.e. cuts separating any two distinguished pairs of vertices ofG, or (iii) ℱ is the set of cuts induced (in a sense) by a ring of subsets of a setT⊆V. In the present work we consider a large class of families of cuts of complete graphs and prove that a family from this class
has the MFMC-property if and only if it is one of (i), (ii), (iii). 相似文献
17.
Vojtěch Rödl 《Combinatorica》1982,2(4):377-383
P. Erdős and A. Hajnal asked the following question. Does there exist a constant ε>0 with the following property: If every
subgraphH of a graphG can be made bipartite by the omission of at most ε|H| edges where |H| denotes the number of vertices ofH thenx(H) ≦ 3.
The aim of this note is to give a negative answer to this question and consider the analogous problem for hypergraphs. The
first was done also by L. Lovász who used a different construction. 相似文献
18.
I. Kátai 《Lithuanian Mathematical Journal》2008,48(3):316-321
We generalize a result of F. Luca and A. Sankaranarayanan by proving that the set of n for which ϕ(1) + ⃛ + ϕ(n) is squareful is of zero density. A similar statement holds for σ (n) instead of ϕ(n) and for some other multiplicative functions.
Dedicated to Professor Eugenijus Manstavičius on his 60th anniversary 相似文献
19.
G. R. T. Hendry 《Periodica Mathematica Hungarica》1990,21(3):205-218
A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply
the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K
k
orK
k
−e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13]. 相似文献
20.
Summary Based on a random sample from the normal cumulative distribution function ϕ(x; μ, σ) with unknown parameters μ and σ, one-sided confidence contours for ϕ(x; μ, σ), −∞<x<∞, and simultaneous confidence intervals for ϕ(y; μ, σ)−ϕ(x; μ, σ), −∞<x<y<∞, are constructed using the method outlined in [3]. Small sample and asymptotic distributions of the relevant statistics
are provided so that the construction could be completely carried out in any practical situation. 相似文献