共查询到20条相似文献,搜索用时 781 毫秒
1.
A dimensional property of graphs is a property P such that every graph G is the intersection of graphs having property P. If P is a dimensional property, we describe a general method for computing the least integer k so that G is the intersection of k graphs having property P. We give simple applications of the method to computing the boxicity, the cubicity, the circular dimension, the rigid circuit dimension, and the overlap dimension, and mention connections to other concepts such as the threshold dimension. 相似文献
2.
This paper considers the so-called distance graph G(n, r, s);its vertices can be identified with the r-element subsets of the set {1, 2,…,n}, and two vertices are joined by an edge if the size of the intersection of the corresponding subsets equals s. Note that, in the case s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s-Ko-Rado problem; they also play an important role in combinatorial geometry and coding theory. We study properties of random subgraphs of the graph G(n, r, s) in the Erd?s-Rényi model, in which each edge is included in the subgraph with a certain fixed probability p independently of the other edges. It is known that if r > 2s + 1, then, for p = 1/2, the size of an independent set is asymptotically stable in the sense that the independence number of a random subgraph is asymptotically equal to that of the initial graph G(n, r, s). This gives rise to the question of how small p must be for asymptotic stability to cease. The main result of this paper is the answer to this question. 相似文献
3.
For a graph G let ℒ( G)=Σ{1/ k contains a cycle of length k}. Erdős and Hajnal [1] introduced the real function f(α)=inf {ℒ ( G)| E(G)|/| V(G)|≧α} and suggested to study its properties. Obviously f(1)=0. We prove f ( k+1/ k)≧(300 k log k) −1 for all sufficiently large k, showing that sparse graphs of large girth must contain many cycles of different lengths. 相似文献
4.
Does there exist a function f( r, n) such that each graph G with Z ( G)≧ f( r, n) contains either a complete subgraph of order r or else two non-neighboring n-chromatic subgraphs? It is known that f( r, 2) exists and we establish the existence of f( r, 3). We also give some interesting results about graphs which do not contain two independent edges. 相似文献
5.
All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphs G, H, let N( G, H) denote the number of subgraphs of G isomorphic to H. Define also, for l≧0, N( l, H)=max N( G, H), where the maximum is taken over all graphs G with l edges. We determine N( l, H) precisely for all l≧0 when H is a disjoint union of two stars, and also when H is a disjoint union of r≧3 stars, each of size s or s+1, where s≧ r. We also determine N( l, H) for sufficiently large l when H is a disjoint union of r stars, of sizes s
1≧ s
2≧…≧ s
r> r, provided ( s
1− s
r) 2< s
1+ s
r−2 r. We further show that if H is a graph with k edges, then the ratio N( l, H)/ l
k tends to a finite limit as l→∞. This limit is non-zero iff H is a disjoint union of stars. 相似文献
6.
A graph is fraternally oriented iff for every three vertices u, ν, w the existence of the edges u → w and ν → w implies that u and ν are adjacent. A directed unicyclic graph is obtained from a unicyclic graph by orienting the unique cycle clockwise and by orienting the appended subtrees from the cycle outwardly. Two directed subtrees s, t of a directed unicyclic graph are proper if their union contains no (directed or undirected) cycle and either they are disjoint or one of them s has its root r( s) in t and contains all the successors of r( s) in t. In the present paper we prove that G is an intersection graph of a family of proper directed subtrees of a directed unicyclic graph iff it has a fraternal orientation such that for every vertex ν, G(Γ inν) is acyclic and G(Γ outν) is the transitive closure of a tree. We describe efficient algorithms for recognizing when such graphs are perfect and for testing isomorphism of proper circular-arc graphs. 相似文献
7.
A variation in the classical Turan extrernal problem is studied. A simple graph G of order n is said to have property Pk if it contains a clique of size k+1 as its subgraph. An n-term nonincreasing nonnegative integer sequence π=(d 1, d 2,⋯, d 2) is said to be graphic if it is the degree sequence of a simple graph G of order n and such a graph G is referred to as a realization of π. A graphic sequence π is said to be potentially P
k-graphic if it has a realization G having property P
k
. The problem: determine the smallest positive even number σ(k, n) such that every n-term graphic sequence π=(d 1, d 2,…, d 2) without zero terms and with degree sum σ(π)=( d
1+ d
2+ …+ d
2) at least σ( k, n) is potentially P k-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. 相似文献
8.
A path P in a graph G is said to be extendable if there exists a path P’ in G with the same endvertices as P such that V( P)⊆ V ( P’) and | V( P’)|=| V( P)|+1. A graph G is path extendable if every nonhamiltonian path in G 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 if G is a graph of order p in which the degree sum of each pair of non-adjacent vertices is at least p+1 and P is a nonextendable path of order k in G then k≤( p+1)/2 and 〈 V ( P)〉≅ K
k
or K
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 in G is at least (3 p−3)/2 then G is path extendable, which strengthen results of Williamson [13]. 相似文献
9.
The concept of the k-pairable graphs was introduced by Zhibo Chen (On k-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism.
In the same paper, Chen also introduced a new graph parameter p( G), called the pair length of a graph G, as the maximum k such that G is k-pairable and p( G) = 0 if G is not k-pairable for any positive integer k. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be
trees. That is, we characterize the trees G with p( G) = 1 and prove that p( G □ H) = p( G) + p( H) when both G and H are trees. 相似文献
10.
The concept of a local k-coloring of a graph G is introduced and the corresponding local k-Ramsey number r
loc
k
(G) is considered. A local k-coloring of G is a coloring of its edges in such a way that the edges incident to any vertex of G are colored with at most k colors. The number r
loc
k
(G) is the minimum m for which K
m
contains a monochromatic copy of G for every local k-coloring of K
m
. The number r
loc
k
(G) is a natural generalization of the usual Ramsey number r
k
(G) defined for usual k-colorings. The results reflect the relationship between r
k
(G) and r
loc
k
(G) for certain classes of graphs.This research was done while under an IREX grant. 相似文献
11.
A coloring of the edges of a graph is called a local k-coloring if every vertex is incident to edges of at most k distinct colors. For a given graph G, the local Ramsey number, r
loc
k
(G), is the smallest integer n such that any local k-coloring of K
n
, (the complete graph on n vertices), contains a monochromatic copy of G. The following conjecture of Gyárfás et al. is proved here: for each positive integer k there exists a constant c = c(k) such that r
loc
k
(G) cr
k
(G), for every connected grraph G (where r
k
(G) is the usual Ramsey number for k colors). Possible generalizations for hypergraphs are considered.On leave from the Institute of Mathematics, Technical University of Warsaw, Poland.While on leave at University of Louisville, Fall 1985. 相似文献
12.
Assume that G is a 3-colourable connected graph with e( G) = 2 v( G) − k, where k≥ 4. It has been shown that s
3( G) ≥ 2
k
−3, where s
r
( G) = P( G, r)/ r! for any positive integer r and P( G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s
3( G) < 2
k
−2, then G contains at most v( G) − k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C
k
by a 2-tree. By using this result, we settle the problem of determining if W( n, s) is χ-unique, where W( n, s) is the graph obtained from the wheel W
n
by deleting all but s consecutive spokes.
Received: January 29, 1999 Final version received: April 8, 2000 相似文献
13.
For integers d≥0, s≥0, a ( d, d+ s)‐ graph is a graph in which the degrees of all the vertices lie in the set { d, d+1, …, d+ s}. For an integer r≥0, an ( r, r+1)‐ factor of a graph G is a spanning ( r, r+1)‐subgraph of G. An ( r, r+1)‐ factorization of a graph G is the expression of G as the edge‐disjoint union of ( r, r+1)‐factors. For integers r, s≥0, t≥1, let f( r, s, t) be the smallest integer such that, for each integer d≥ f( r, s, t), each simple ( d, d+ s) ‐graph has an ( r, r+1) ‐factorization with x ( r, r+1) ‐factors for at least t different values of x. In this note we evaluate f( r, s, t). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 257‐268, 2009 相似文献
14.
For a finite or infinite graph G, the Gallai graph ( G) of G is defined as the graph whose vertex set is the edge set E(G) of G; two distinct edges of G are adjacent in ( G) if they are incident but do not span a triangle in G. For any positive integer t, the tth iterated Gallai graph
t
( G) of G is defined by (
t–1( G)), where 0( G):= G. A graph is said to be Gallai-mortal if some of its iterated Gallai graphs finally equals the empty graph. In this paper we characterize Gallai-mortal graphs in several ways. 相似文献
15.
For integers p and s satisfying 2 ? s ? p ? 1, let m( p,s) denote the maximum number of edges in a graph G of order p such that the minimum degree in the hamiltonian path graph of G equals s. The values of m( p, s) are determined for 2 ? s ? p/2 and for (2 p ? 2)/3 ? s ? p ? 1, and upper and lower bounds on m( p, s) are obtained for p/2 < s < (2 p ? 2)/3. 相似文献
16.
For some integer k0 and two graph parameters π and τ, a graph G is called πτ( k)- perfect, if π( H)− τ( H) k for every induced subgraph H of G. For r1 let αr and γr denote the r-(distance)-independence and r-(distance)-domination number, respectively. In (J. Graph Theory 32 (1999) 303–310), I. Zverovich gave an ingenious complete characterization of α1γ1( k)-perfect graphs in terms of forbidden induced subgraphs. In this paper we study αrγs( k)-perfect graphs for r, s1. We prove several properties of minimal αrγs( k)-imperfect graphs. Generalizing Zverovich's main result in (J. Graph Theory 32 (1999) 303–310), we completely characterize α2r−1γr( k)-perfect graphs for r1. Furthermore, we characterize claw-free α2γ2( k)-perfect graphs. 相似文献
17.
For any integer k e 1 the k- path graph P k (G) of a graph G has all length- k subpaths of G as vertices, and two such vertices are adjacent whenever their union (as subgraphs of G) forms a path or cycle with k + 1 edges. For k = 1 we get the well-known line graph P 1 (G) = L(G). Iterated k-path graphs P t k( G) are defined as usual by P t k (G) := P k( P t?1 k( G)) if t < 1, and by P 1 k( G): = P k( G). A graph G is P k - periodic if it is isomorphic to some iterated k-path graph of itself; it P k - converges if some iterated k-path graph of G is P k -periodic. A graph has infinite P k - depth if for any positive integer t there is a graph H such that P t k( H) ? G. In this paper P k - periodic if it is isomorphic to some iterated k-path graph of itself; it P k - converges if some iterated k-path graph of G is P k -periodic graphs, P k - periodic if it is isomorphic to some iterated k-path graph of itself; it P k - converges if some iterated k-path graph of G is P k -convergent graphs, and graphs with infinite P k - periodic if it is isomorphic to some iterated k-path graph of itself; it P k - converges if some iterated k-path graph of G is P k -depth are characterized inside some subclasses of the class of locally finite graphs for k = 1, 2. 相似文献
18.
Given a graph G and an integer k ≥ 1, let α( G, k) denote the number of k‐independent partitions of G. Let ?? ?s( p,q) (resp., ?? 2?s( p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph Kp,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α( G,3), where G ∈ ?? ?s( p,q) and 0 ≤ s ≤ ( p ? 1)( q ? 1) (resp., G ∈ ?? 2?s( p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ?s( p,q) (resp., G ∈ ?? 2?s ( p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ?? ?si( p+ i,q? i) where max and si = s ? i(p?q+ i) (resp., a subset of ?? 2?s( p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2 q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from Kp,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001 相似文献
19.
For a graph G and an integer k ≥ 1, let ς k( G) = dG( vi): { v1, …, vk} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a ( s + 2)-connected graph. Then G has a cycle of length ≥ min{| V( G)|, ς 2( G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a ( k + s − 1)-connected graph. Then G has a cycle of length ≥ min{| V( G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998 相似文献
20.
The quasi‐random theory for graphs mainly focuses on a large equivalent class of graph properties each of which can be used as a certificate for randomness. For k ‐graphs (i.e., k ‐uniform hypergraphs), an analogous quasi‐random class contains various equivalent graph properties including the k ‐ discrepancy property (bounding the number of edges in the generalized induced subgraph determined by any given ( k ‐ 1) ‐graph on the same vertex set) as well as the k ‐ deviation property (bounding the occurrences of “octahedron”, a generalization of 4 ‐cycle). In a 1990 paper (Chung, Random Struct Algorithms 1 (1990) 363‐382), a weaker notion of l ‐discrepancy properties for k ‐graphs was introduced for forming a nested chain of quasi‐random classes, but the proof for showing the equivalence of l ‐discrepancy and l ‐deviation, for 2 ≤ l < k, contains an error. An additional parameter is needed in the definition of discrepancy, because of the rich and complex structure in hypergraphs. In this note, we introduce the notion of ( l, s) ‐discrepancy for k ‐graphs and prove that the equivalence of the ( k, s) ‐discrepancy and the s ‐deviation for 1 ≤ s ≤ k. We remark that this refined notion of discrepancy seems to point to a lattice structure in relating various quasi‐random classes for hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 相似文献
|