首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
The clique graph K(G) of a graph is the intersection graph of maximal cliques of G. The iterated clique graph Kn(G) is inductively defined as K(Kn?1(G)) and K1(G) = K(G). Let the diameter diam(G) be the greatest distance between all pairs of vertices of G. We show that diam(Kn(G)) = diam(G) — n if G is a connected chordal graph and n ≤ diam(G). This generalizes a similar result for time graphs by Bruce Hedman.  相似文献   

2.
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  相似文献   

3.
In this paper, we study the edge clique cover number of squares of graphs. More specifically, we study the inequality θ(G2)θ(G) where θ(G) is the edge clique cover number of a graph G. We show that any graph G with at most θ(G) vertices satisfies the inequality. Among the graphs with more than θ(G) vertices, we find some graphs violating the inequality and show that dually chordal graphs and power-chordal graphs satisfy the inequality. Especially, we give an exact formula computing θ(T2) for a tree T.  相似文献   

4.
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.  相似文献   

5.
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.  相似文献   

6.
The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum clique size ω(G) = m, then i(G) ? [1 + o(1)]m/log2 m and this result is best possible, even for split graphs (chordal graphs whose complement is also chordal).  相似文献   

7.
Let i be a positive integer. We generalize the chromatic number X(G) of G and the clique number o(G) of G as follows: The i-chromatic number of G, denoted by X(G), is the least number k for which G has a vertex partition V1, V2,…, Vk such that the clique number of the subgraph induced by each Vj, 1 ≤ jk, is at most i. The i-clique number, denoted by oi(G), is the i-chromatic number of a largest clique in G, which equals [o(G/i]. Clearly X1(G) = X(G) and o1(G) = o(G). An induced subgraph G′ of G is an i-transversal iff o(G′) = i and o(GG′) = o(G) − i. We generalize the notion of perfect graphs as follows: (1) A graph G is i-perfect iff Xi(H) = oi(H) for every induced subgraph H of G. (2) A graph G is perfectly i-transversable iff either o(G) ≤ i or every induced subgraph H of G with o(H) > i contains an i-transversal of H. We study the relationships among i-perfect graphs and perfectly i-transversable graphs. In particular, we show that 1-perfect graphs and perfectly 1-transversable graphs both coincide with perfect graphs, and that perfectly i-transversable graphs form a strict subset of i-perfect graphs for every i ≥ 2. We also show that all planar graphs are i-perfect for every i ≥ 2 and perfectly i-transversable for every i ≥ 3; the latter implies a new proof that planar graphs satisfy the strong perfect graph conjecture. We prove that line graphs of all triangle-free graphs are 2-perfect. Furthermore, we prove for each i greater than or equal to2, that the recognition of i-perfect graphs and the recognition of perfectly i-transversable graphs are intractable and not likely to be in co-NP. We also discuss several issues related to the strong perfect graph conjecture. © 1996 John Wiley & Sons, Inc.  相似文献   

8.
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.  相似文献   

9.
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.  相似文献   

10.
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.  相似文献   

11.
For 1 ≤ dk, let Kk/d be the graph with vertices 0, 1, …, k ? 1, in which ij if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χc(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to Kk/d. The circular clique number ωc(G) of G is the maximum of those k/d for which Kk/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χc(H) = ωc(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, NG[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, NG[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P5 (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph Kk/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005  相似文献   

12.
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.  相似文献   

13.
Let G be a connected claw-free graph on n vertices. Let ς3(G) be the minimum degree sum among triples of independent vertices in G. It is proved that if ς3(G) ≥ n − 3 then G is traceable or else G is one of graphs Gn each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K3. Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if ς3(G) ≥ nk, n > ν(k) and G is non-traceable, then G is a factor of a graph Gn. Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that ς3(G) ≥ . This contrasts sharply with known results on NP-completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998  相似文献   

14.
Let G be an undirected connected graph that is not a path. We define h(G) (respectively, s(G)) to be the least integer m such that the iterated line graph Lm(G) has a Hamiltonian cycle (respectively, a spanning closed trail). To obtain upper bounds on h(G) and s(G), we characterize the least integer m such that Lm(G) has a connected subgraph H, in which each edge of H is in a 3-cycle and V(H) contains all vertices of degree not 2 in Lm(G). We characterize the graphs G such that h(G) — 1 (respectively, s(G)) is greater than the radius of G.  相似文献   

15.
The graph resulting from contracting edge e is denoted as G/e and the graph resulting from deleting edge e is denoted as Ge. An edge e is diameter-essential if diam(G/e) < diam(G), diameter-increasing if diam(Ge) < diam(G), and diameter-vital if it is both diameter-essential and diameter-increasing. We partition the edges that are not diameter-vital into three categories. In this paper, we study realizability questions relating to the number of edges that are not diameter-vital in the three defined categories. A graph is diameter-vital if all its edges are diameter-vital. We give a structural characterization of diameter-vital graphs.  相似文献   

16.
Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if pk + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers ki and pk 2/4 + i + 1.  相似文献   

17.
Bo-Jr Li 《Discrete Mathematics》2008,308(11):2075-2079
A clique in a graph G is a complete subgraph of G. A clique covering (partition) of G is a collection C of cliques such that each edge of G occurs in at least (exactly) one clique in C. The clique covering (partition) numbercc(G) (cp(G)) of G is the minimum size of a clique covering (partition) of G. This paper gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained by McGuinness and Rees [On the number of distinct minimal clique partitions and clique covers of a line graph, Discrete Math. 83 (1990) 49-62]. We also employ the proof techniques to give an alternative proof for the De Brujin-Erd?s Theorem.  相似文献   

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

19.
For any graph G, let i(G) and μ;(G) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers m and n, the lower Ramsey number s(m, n) is the largest integer p so that every graph of order p has i(G) ≤ m or μ;(G) ≤ n. In this paper we give several new lower bounds for s (m, n) as well as determine precisely the values s(1, n).  相似文献   

20.
The sphericity sph(G) of a graph G is the minimum dimension d for which G is the intersection graph of a family of congruent spheres in Rd. The edge clique cover number θ(G) is the minimum cardinality of a set of cliques (complete subgraphs) that covers all edges of G. We prove that if G has at least one edge, then sph(G)?θ(G). Our upper bound remains valid for intersection graphs defined by balls in the Lp-norm for 1?p?∞.  相似文献   

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

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