共查询到20条相似文献,搜索用时 0 毫秒
1.
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. 相似文献
2.
3.
4.
5.
6.
We examine the problem of finding a graph G whose nth iterated clique graph has diameter equal to the diameter of G plus n. 相似文献
7.
Relationships between the following graph invariants are studied: The node clique cover number, θ0(>G); the clique cover number θ1(G); node independence number, β0(G); and an edge independence number, β′1(G), We extend a theorem of Choudum, Parthasarathy and Ravindra with further statements equivalent to θ0(G) = θ1(G). More general results regarding the inequality θ0(G) ? 01(G) are presented. 相似文献
8.
9.
We consider finite, undirected, and simple graphs G of order n(G) and minimum degree δ(G). The connectivity κ(G) for a connected graph G is defined as the minimum cardinality over all vertex‐cuts. If κ(G) < δ(G), then Topp and Volkmann 7 showed in 1993 for p‐partite graphs G that As a simple consequence, Topp and Volkmann obtained for p‐partite graphs G the identity κ(G) = δ(G), if In this article, we will show that these results remain true for graphs G with ω(G) ≤ p, where ω(G) denotes the clique number of G. Since each p‐partite graph G satisfies ω(G) ≤ p, this generalizes the results of Topp and Volkmann. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 7–14, 2006 相似文献
10.
For a vertex v of a graph G, we denote by d(v) the degree of v. The local connectivity κ(u, v) of two vertices u and v in a graph G is the maximum number of internally disjoint u –v paths in G, and the connectivity of G is defined as κ(G)=min{κ(u, v)|u, v∈V(G)}. Clearly, κ(u, v)?min{d(u), d(v)} for all pairs u and v of vertices in G. Let δ(G) be the minimum degree of G. We call a graph G maximally connected when κ(G)=δ(G) and maximally local connected when for all pairs u and v of distinct vertices in G. In 2006, Hellwig and Volkmann (J Graph Theory 52 (2006), 7–14) proved that a connected graph G with given clique number ω(G)?p of order n(G) is maximally connected when As an extension of this result, we will show in this work that these conditions even guarantee that G is maximally local connected. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 192–197, 2010 相似文献
11.
Hiroshi Suzuki 《Journal of Algebraic Combinatorics》2014,40(1):233-244
Let Γ=(X,R) be a connected graph. Then Γ is said to be a completely regular clique graph of parameters (s,c) with s≥1 and c≥1, if there is a collection \(\mathcal{C}\) of completely regular cliques of size s+1 such that every edge is contained in exactly c members of \(\mathcal{C}\) . In this paper, we show that the parameters of \(C\in\mathcal{C}\) as a completely regular code do not depend on \(C\in\mathcal{C}\) . As a by-product we have that all completely regular clique graphs are distance-regular whenever \(\mathcal {C}\) consists of edges. We investigate the case when Γ is distance-regular, and show that Γ is a completely regular clique graph if and only if it is a bipartite half of a distance-semiregular graph. 相似文献
12.
13.
The clique graph of a graph G is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques have a non-empty intersection. A graph is self-clique if it is isomorphic to its clique graph. We give a new characterization of the set of all connected self-clique graphs having all cliques but two of size 2. 相似文献
14.
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. 相似文献
15.
16.
Robert F. Bailey 《Discrete Mathematics》2018,341(6):1613-1619
A resolving set for a graph is a collection of vertices , chosen so that for each vertex , the list of distances from to the members of uniquely specifies . The metric dimension is the smallest size of a resolving set for . We consider the metric dimension of two families of incidence graphs: incidence graphs of symmetric designs, and incidence graphs of symmetric transversal designs (i.e. symmetric nets). These graphs are the bipartite distance-regular graphs of diameter 3, and the bipartite, antipodal distance-regular graphs of diameter 4, respectively. In each case, we use the probabilistic method in the manner used by Babai to obtain bounds on the metric dimension of strongly regular graphs, and are able to show that (where is the number of vertices). 相似文献
17.
Fǎnicǎ Gavril 《Discrete Mathematics》1977,19(2):159-165
We define a family of graphs, called the clique separable graphs, characterized by the fact that they have completely connected cut sets by which we decompose them into parts such that when no further decomposition is possible we have a set of simple subgraphs. For example the chordal graphs and the i-triangulated graphs are clique separable graphs.The purpose of this paper is to describe polynomial time algorithms for the recognition of the clique separable graphs and for finding them a minimum coloring and a maximum clique. 相似文献
18.
Nicola Apollonio 《Discrete Applied Mathematics》2011,159(11):1166-1175
We present a unifying procedure for recognizing intersection graphs of Helly families of paths in a tree and their clique graphs. The Helly property makes it possible to look at these recognition problems as variants of the Graph Realization Problem, namely, the problem of recognizing Edge-Path-Tree matrices. Our result heavily relies on the notion of pie introduced in [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinatorial Theory, Series B 38 (1985) 8-22] and on the observation that Helly Edge-Path-Tree matrices form a self-dual class of Helly matrices. Coupled to the notion of reduction presented in the paper, these facts are also exploited to reprove and slightly refine some known results for Edge-Path-Tree graphs. 相似文献
19.
Zoltn Füredi 《Random Structures and Algorithms》1990,1(2):183-189
Here it is proved that for almost all simple graphs over n vertices one needs Ω(n4/3(log n)?4/3) extra vertices to obtain them as a double competition graph of a digraph. on the other hand O(n5/3) extra vertices are always sufficient. Several problems remain open. 相似文献
20.
Kerstin Waas 《Transactions of the American Mathematical Society》1999,351(3):1043-1062
R. Diestel conjectured that an infinite graph contains a topologically end-faithful forest if and only if its end space is metrizable. We prove this conjecture for uniform end spaces.