首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that vivje(G) for vivj if and only if |f(vi) ? f(vj)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K2(G), and inductively, denote K(Km?1(G)) by Km(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kn(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived.  相似文献   

2.
A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman described examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(Ki(G)) = diam(G) + i. Examples satisfying this equality for i = 2 have been described by Peyrat, Rall, and Slater and independently by Balakrishnan and Paulraja. The authors of the former work also solved the case i = 3 and i = 4 and conjectured that such graphs exist for every positive integer i. The cases i ≥ 5 remained open. In the present article, we prove their conjecture. For each positive integer i, we describe a family of graphs G such that diam(Ki(G)) = diam(G) + i. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 147–154, 1998  相似文献   

3.
The clique graph K(G) of a simple graph G is the intersection graph of its maximal complete subgraphs, and we define iterated clique graphs by K0(G)=G, Kn+1(G)=K(Kn(G)). We say that two graphs are homotopy equivalent if their simplicial complexes of complete subgraphs are so. From known results, it can be easily inferred that Kn(G) is homotopy equivalent to G for every n if G belongs to the class of clique-Helly graphs or to the class of dismantlable graphs. However, in both of these cases the collection of iterated clique graphs is finite up to isomorphism. In this paper, we show two infinite classes of clique-divergent graphs that satisfy G?Kn(G) for all n, moreover Kn(G) and G are simple-homotopy equivalent. We provide some results on simple-homotopy type that are of independent interest.  相似文献   

4.
For a graph G, letG′(G″) denote an orientation ofG having maximum (minimum respectively) finite diameter. We show that the length of the longest path in any 2-edge connected (undirected) graph G is precisely diam(G′). LetK(m l ,m 2,...,m n) be the completen-partite graph with parts of cardinalitiesm 1 m2, …,m n . We prove that ifm 1 = m2 = … =m n = m,n ≥ 3, then diam(K″(m1,m2,...,mn)) = 2, unless m=1 andn = 4.  相似文献   

5.
On clique convergent graphs   总被引:1,自引:0,他引:1  
A graphG isconvergent when there is some finite integern 0, such that then-th iterated clique graphK n(G) has only one vertex. The smallest suchn is theindex ofG. TheHelly defect of a convergent graph is the smallestn such thatK n(G) is clique Helly, that is, its maximal cliques satisfy the Helly property. Bandelt and Prisner proved that the Helly defect of a chordal graph is at most one and asked whether there is a graph whose Helly defect exceeds the difference of its index and diameter by more than one. In the present paper an affirmative answer to the question is given. For any arbitrary finite integern, a graph is exhibited, the Helly defect of which exceeds byn the difference of its index and diameter.  相似文献   

6.
We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graphG, a familyG={G 1,G 2,...,G k } is called aclique cover ofG if (i) eachG i is a clique or a bipartite clique, and (ii) the union ofG i isG. The size of the clique coverG is defined as ∑ i=1 k n i , wheren i is the number of vertices inG i . Our main result is that there are visibility graphs ofn nonintersecting line segments in the plane whose smallest clique cover has size Ω(n 2/log2 n). An upper bound ofO(n 2/logn) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of sizeO(nlog3 n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n logn). The work by the first author was supported by National Science Foundation Grant CCR-91-06514. The work by the second author was supported by a USA-Israeli BSF grant. The work by the third author was supported by National Science Foundation Grant CCR-92-11541.  相似文献   

7.
8.
A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graphK(G) of a graph G is the intersection graph of its cliques. The iterated clique graphKi(G) of G is defined by K0(G)=G and Ki+1(G)=K(Ki(G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph K-converges, if it is K-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems.  相似文献   

9.
An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ=(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ=*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ=(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ=(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ=* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ=*(G(n,p)) = O?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009  相似文献   

10.
An affine graph is a pair (G,σ) where G is a graph and σ is an automorphism assigning to each vertex of G one of its neighbors. On one hand, we obtain a structural decomposition of any affine graph (G,σ) in terms of the orbits of σ. On the other hand, we establish a relation between certain colorings of a graph G and the intersection graph of its cliques K(G). By using the results we construct new examples of expansive graphs. The expansive graphs were introduced by Neumann-Lara in 1981 as a stronger notion of the K-divergent graphs. A graph G is K-divergent if the sequence |V(Kn(G))| tends to infinity with n, where Kn+1(G) is defined by Kn+1(G)=K(Kn(G)) for n?1. In particular, our constructions show that for any k?2, the complement of the Cartesian product Ck, where C is the cycle of length 2k+1, is K-divergent.  相似文献   

11.
A k-decomposition (G1,…,Gk) of a graph G is a partition of its edge set to form k spanning subgraphs G1,…,Gk. The classical theorem of Nordhaus and Gaddum bounds χ(G1) + χ(G2) and χ(G1)χ(G2) over all 2-decompositions of Kn. For a graph parameter p, let p(k;G) denote the maximum of over all k-decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;Kn) = χ(2;Kn) = χℓ(2;Kn) = σ(2;Kn) = n + 1. We obtain lower and upper bounds for ω(k;Kn), χ(k;Kn), χℓ(k;Kn), and σ(k;Kn). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface. © 2005 Wiley Periodicals, Inc. J Graph Theory  相似文献   

12.
Even graphs     
A nontrivial connected graph G is called even if for each vertex v of G there is a unique vertex v such that d(v, v ) = diam G. Special classes of even graphs are defined and compared to each other. In particular, an even graph G is called symmetric if d(u, v) + d(u, v ) = diam G for all u, vV(G). Several properties of even and symmetric even graphs are stated. For an even graph of order n and diameter d other than an even cycle it is shown that n ≥ 3d – 1 and conjectured that n ≥ 4d – 4. This conjecture is proved for symmetric even graphs and it is shown that for each pair of integers n, d with n even, d ≥ 2 and n ≥ 4d – 4 there exists an even graph of order n and diameter d. Several ways of constructing new even graphs from known ones are presented.  相似文献   

13.
The tree partition number of an r‐edge‐colored graph G, denoted by tr(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t2(K(n1, n2,…, nk)) of the complete k‐partite graph K(n1, n2,…, nk). In particular, we prove that t2(K(n, m)) = ? (m‐2)/2n? + 2, where 1 ≤ nm. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005  相似文献   

14.
The inflation GI of a graph G with n(G) vertices and m(G) edges is obtained by replacing every vertex of degree d of G by a clique Kd. We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if γ denotes the domination number of a graph, γ(GI) − ir(GI) can be arbitrarily large, IR(GI) ≤ m(G) and IR(GI) ≤ n2(G)/4. These results disprove a conjecture of Dunbar and Haynes (Congr. Num. 118 (1996), 143–154) and answer another open question. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 97–104, 1998  相似文献   

15.
Let G be a connected plane graph, D(G) be the corresponding link diagram via medial construction, and μ(D(G)) be the number of components of the link diagram D(G). In this paper, we first provide an elementary proof that μ(D(G))≤n(G)+1, where n(G) is the nullity of G. Then we lay emphasis on the extremal graphs, i.e. the graphs with μ(D(G))=n(G)+1. An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from K1 by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs.  相似文献   

16.
The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.  相似文献   

17.
Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.  相似文献   

18.
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)!!].  相似文献   

19.
With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph Lm(G) of G is defined to be L(Lm-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ np ? 3, if the removal of any k vertices, 0 ≤ kn, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L2(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L2(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that Lm(G) is n-Hamiltonian for every mk is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs.  相似文献   

20.
The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K3‐free and K4‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号