共查询到20条相似文献,搜索用时 15 毫秒
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.
Claude Berge 《Combinatorica》1982,2(3):213-222
Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ1, μ2, ..., μk such tht |μi ∩S|=1 for alli.
Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic
number; here again, we do not know if there exists an optimal coloring (S
1,S
2, ...,S
k) and a path μ such that |μ ∩S
i|=1 for alli.
In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable
setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal
coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the
perfect graph conjecture.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
3.
Mitre C. Dourado Fábio Protti Dieter Rautenbach Jayme L. Szwarcfiter 《Graphs and Combinatorics》2012,28(3):333-345
A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G) ≥ k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay
between these properties and upper bounds on the convexity number. 相似文献
4.
Sanming Zhou 《Monatshefte für Mathematik》2003,139(1):69-81
With any G-symmetric graph Γ admitting a nontrivial G-invariant partition , we may associate a natural “cross-sectional” geometry, namely the 1-design in which for and if and only if α is adjacent to at least one vertex in C, where and is the neighbourhood of B in the quotient graph of Γ with respect to . In a vast number of cases, the dual 1-design of contains no repeated blocks, that is, distinct vertices of B are incident in with distinct subsets of blocks of . The purpose of this paper is to give a general construction of such graphs, and then prove that it produces all of them.
In particular, we show that such graphs can be reconstructed from and the induced action of G on . The construction reveals a close connection between such graphs and certain G-point-transitive and G-block-transitive 1-designs. By using this construction we give a characterization of G-symmetric graphs such that there is at most one edge between any two blocks of . This leads to, in a subsequent paper, a construction of G-symmetric graphs such that and each is incident in with vertices of B.
The work was supported by a discovery-project grant from the Australian Research Council.
Received April 24, 2001; in revised form October 9, 2002
Published online May 9, 2003 相似文献
5.
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. 相似文献
6.
Carsten Thomassen 《Combinatorica》2001,21(2):321-333
Dedicated to the memory of Paul Erdős
A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs
of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph.
Received May 13, 1999/Revised June 19, 2000 相似文献
7.
A graph G is
inexhaustible if whenever a vertex of G is deleted the remaining graph is
isomorphic to G. We address a
question of Cameron [6], who asked which countable graphs are
inexhaustible. In particular, we prove that there are continuum
many countable inexhaustible graphs with properties in common
with the infinite random graph, including adjacency properties
and universality. Locally finite inexhaustible graphs and
forests are investigated, as is a semigroup structure on the
class of inexhaustible graphs. We extend a result of [7] on
homogeneous inexhaustible graphs to pseudo-homogeneous
inexhaustible graphs.The authors gratefully acknowledge support from the
Natural Science and Engineering Research Council of Canada
(NSERC). 相似文献
8.
H. A. Jung 《Combinatorica》1981,1(3):285-288
Results involving automorphisms and fragments of infinite graphs are proved. In particular for a given fragmentC and a vertex-transitive subgroupG of the automorphism group of a connected graph there exists σ≠G such that σ[C] ⊂C. This proves the countable case of a conjecture of L. Babai and M. E. Watkins concerning graphs allowing a vertex-transitive
torsion group action.
Dedicated to Prof. K. Wagner on his 70th birthday 相似文献
9.
Vladimir Nikiforov 《Linear algebra and its applications》2010,432(9):2243-2256
Let G be a graph with n vertices and μ(G) be the largest eigenvalue of the adjacency matrix of G. We study how large μ(G) can be when G does not contain cycles and paths of specified order. In particular, we determine the maximum spectral radius of graphs without paths of given length, and give tight bounds on the spectral radius of graphs without given even cycles. We also raise a number of open problems. 相似文献
10.
Cycles in weighted graphs 总被引:2,自引:0,他引:2
A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4]. 相似文献
11.
Jun-Jie Pan 《Discrete Mathematics》2006,306(17):2091-2096
An isometric path between two vertices in a graph G is a shortest path joining them. The isometric path number of G, denoted by ip(G), is the minimum number of isometric paths needed to cover all vertices of G. In this paper, we determine exact values of isometric path numbers of complete r-partite graphs and Cartesian products of 2 or 3 complete graphs. 相似文献
12.
IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic
number and no short cycles. In particular, we solve a problem of J. Spencer.
Dedicated to Paul Erdős on his seventieth birthday 相似文献
13.
How to decrease the diameter of triangle-free graphs 总被引:3,自引:0,他引:3
Assume that G is a triangle-free graph. Let be the minimum number of edges one has to add to G to get a graph of diameter at most d which is still triangle-free. It is shown that for connected graphs of order n and of fixed maximum degree. The proof is based on relations of and the clique-cover number of edges of graphs. It is also shown that the maximum value of over (triangle-free) graphs of order n is . The behavior of is different, its maximum value is . We could not decide whether for connected (triangle-free) graphs of order n with a positive ε.
Received: October 12, 1997 相似文献
14.
Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied. 相似文献
15.
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 相似文献
16.
Laurent Miclo 《Probability Theory and Related Fields》1999,114(4):431-485
Let G be a finite and connected graph, we will note by l(G) the maximum length of an injective path in G. We will show (by two dictinct proofs, one using sub-trees of G and the other based on multiflows of paths) that sup
(P,μ)∈?(G)
I(P, μ)/λ(P, μ) = l(G), where the supremum is taken over all Markovian kernels P reversible with respect to a probability μ and whose allowed transitions are given by the edges of G, and where I(P, μ) (respectively λ(P, μ)) is the isoperimetric constant (resp. the spectral gap) associated to the couple (P, μ). Then we will study more precisely the same supremum, but where the probability μ is also fixed. These results give optimal
minorations of the spectral gap which are linear with respect to the isoperimetric constant (and not quadratic, as in the
Cheeger inequality), and we will give several examples on infinite graphs.
Re?u: 12 ao?t 1997 / Version révisée: 9 novembre 1998 相似文献
17.
Cam McLeman 《Linear algebra and its applications》2011,435(5):998-1007
We introduce a new invariant, the coronal of a graph, and use it to compute the spectrum of the corona G°H of two graphs G and H. In particular, we show that this spectrum is completely determined by the spectra of G and H and the coronal of H. Previous work has computed the spectrum of a corona only in the case that H is regular. We then explicitly compute the coronals for several families of graphs, including regular graphs, complete n-partite graphs, and paths. Finally, we use the corona construction to generate many infinite families of pairs of cospectral graphs. 相似文献
18.
Given two graphs A and G, we write if there is a homomorphism of A to G and if there is no such homomorphism. The graph G is -free if, whenever both a and c are adjacent to b and d, then a = c or b = d. We will prove that if A and B are connected graphs, each containing a triangle and if G is a -free graph with and , then (here " denotes the categorical product).
Received August 31, 1998/Revised April 19, 2000
RID="†"
ID="†" Supported by NSERC of Canada Grant #691325. 相似文献
19.
《Quaestiones Mathematicae》2013,36(4):537-548
AbstractFor a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G. 相似文献
20.
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. 相似文献