共查询到20条相似文献,搜索用时 31 毫秒
1.
Associated to a simple undirected graph G is a simplicial complex ΔG whose faces correspond to the independent sets of G. We call a graph G shellable if ΔG is a shellable simplicial complex in the non-pure sense of Björner-Wachs. We are then interested in determining what families of graphs have the property that G is shellable. We show that all chordal graphs are shellable. Furthermore, we classify all the shellable bipartite graphs; they are precisely the sequentially Cohen-Macaulay bipartite graphs. We also give a recursive procedure to verify if a bipartite graph is shellable. Because shellable implies that the associated Stanley-Reisner ring is sequentially Cohen-Macaulay, our results complement and extend recent work on the problem of determining when the edge ideal of a graph is (sequentially) Cohen-Macaulay. We also give a new proof for a result of Faridi on the sequentially Cohen-Macaulayness of simplicial forests. 相似文献
2.
Chuan-Min Lee 《Annals of Operations Research》2010,181(1):21-66
A maximum-clique transversal set of a graph G is a subset of vertices intersecting all maximum cliques of G. The maximum-clique transversal set problem is to find a maximum-clique transversal set of G of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced
the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we introduce the concept of maximum-clique perfect and some variations of the maximum-clique transversal set problem such as the {k}-maximum-clique, k-fold maximum-clique, signed maximum-clique, and minus maximum-clique transversal problems. We show that balanced graphs,
strongly chordal graphs, and distance-hereditary graphs are maximum-clique perfect. Besides, we present a unified approach
to these four problems on strongly chordal graphs and give complexity results for the following classes of graphs: split graphs,
balanced graphs, comparability graphs, distance-hereditary graphs, dually chordal graphs, doubly chordal graphs, chordal graphs,
planar graphs, and triangle-free graphs. 相似文献
3.
A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we characterize well covered simplicial, chordal and circular arc graphs. © 1996 John Wiley & Sons, Inc. 相似文献
4.
Yukio Shibata 《Journal of Graph Theory》1988,12(3):421-428
We introduce the notion of the boundary clique and the k-overlap clique graph and prove the following: Every incomplete chordal graph has two nonadjacent simplicial vertices lying in boundary cliques. An incomplete chordal graph G is k-connected if and only if the k-overlap clique graph gk(G) is connected. We give an algorithm to construct a clique tree of a connected chordal graph and characterize clique trees of connected chordal graphs using the algorithm. 相似文献
5.
In a 3-connected planar triangulation, every circuit of length ≥ 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are “separated” by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In this paper we prove his conjecture, that if G is simple and 3-connected and every circuit of length ≥ 4 has at least two “bridges,” then G may be built up by “clique-sums” starting from complete graphs and planar triangulations. This is a generalization of Dirac's theorem about chordal graphs. 相似文献
6.
We introduce the notion of k-hyperclique complexes, i.e., the largest simplicial complexes on the set [n] with a fixed k-skeleton. These simplicial complexes are a higher-dimensional analogue of clique (or flag) complexes (case k = 2) and they are a rich new class of simplicial complexes. We show that Dirac’s theorem on chordal graphs has a higher-dimensional
analogue in which graphs and clique complexes get replaced, respectively, by simplicial matroids and k-hyperclique complexes. We prove also a higher-dimensional analogue of Stanley’s reformulation of Dirac’s theorem on chordal
graphs.
相似文献
7.
There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries. To this end, we propose the first-order theory of almost all graphs by presenting Axiom n which states that for each sequence of 2n distinct vertices in a graph (u1, …, un, v1, …, vn), there exists another vertex w adjacent to each u1 and not adjacent to any vi. A simple counting argument proves that for each n, almost all graphs satisfy Axiom n. It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graph H, almost all graphs have an induced subgraph isomorphic to H. (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all grpahs are connected wiht diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicial complexes. 相似文献
8.
Demet Taylan 《Order》2016,33(3):459-476
We generalize some homotopy calculation techniques such as splittings and matching trees that are introduced for the computations in the case of the independence complexes of graphs to arbitrary simplicial complexes. We then exemplify their efficiency on some simplicial complexes, the devoid complexes of graphs, \(\mathcal {D}(G;\mathcal {F})\) whose faces are vertex subsets of G that induce \(\mathcal {F}\)-free subgraphs, where G is a multigraph and \(\mathcal {F}\) is a family of multigraphs. Additionally, we compute the homotopy type of dominance complexes of chordal graphs. 相似文献
9.
A vertex is simplicial if the vertices of its neighborhood are pairwise adjacent. It is known that, for every vertex v of a chordal graph, there exists a simplicial vertex among the vertices at maximum distance from v. Here we prove similar properties in other classes of graphs related to that of chordal graphs. Those properties will not be in terms of simplicial vertices, but in terms of other types of vertices that are used to characterize those classes. 相似文献
10.
Let ?? and ?? be graph classes. We say that ?? has the Erd?s–Pósa property for ?? if for any graph G ∈??, the minimum vertex covering of all ??‐subgraphs of G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that belongs to ??). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ?? is the class of all graphs that can be contracted to a fixed planar graph H, then ?? has the Erd?s–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when ?? is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011 相似文献
11.
We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices. 相似文献
12.
The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than
4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this
conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity. 相似文献
13.
We give a generalization of Eagon-Reiner’s theorem relating Betti numbers of the Stanley-Reisner ideal of a simplicial complex and the CMt property of its Alexander dual. Then we characterize bi-CMt bipartite graphs and bi-CMt chordal graphs. These are generalizations of recent results due to Herzog and Rahimi. 相似文献
14.
We call a simple graph G a 4-cycled graph if either it has no edges or every edge of it is contained in an induced 4-cycle of G. Our interest on 4-cycled graphs is motivated by the fact that their clique complexes play an important role in the simple-homotopy
theory of simplicial complexes. We prove that the minimal simple models within the category of flag simplicial complexes are
exactly the clique complexes of some 4-cycled graphs. We further provide structural properties of 4-cycled graphs and describe
constructions yielding such graphs. We characterize 4-cycled cographs, and 4-cycled graphs arising from finite chessboards.
We introduce a family of inductively constructed graphs, the external extensions, related to an arbitrary graph, and determine
the homotopy type of the independence complexes of external extensions of some graphs. 相似文献
15.
Andreas Brandstädt Konrad K. Dabrowski Shenwei Huang Daniël Paulusma 《Journal of Graph Theory》2017,86(1):42-77
A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique‐width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co‐gem are the only two 1‐vertex P4‐extensions H for which the class of H‐free chordal graphs has bounded clique‐width. In fact we prove that bull‐free chordal and co‐chair‐free chordal graphs have clique‐width at most 3 and 4, respectively. In particular, we find four new classes of H‐free chordal graphs of bounded clique‐width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H‐free chordal graphs has bounded clique‐width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of ‐free graphs has bounded clique‐width via a reduction to K4‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H‐free weakly chordal graphs. 相似文献
16.
A. M. H. Gerards 《Journal of Graph Theory》1988,12(1):73-83
We give a class of graphs G for which there exists a homomorphism (= adjacency preserving map) from V(G) to V(C), where C is the shortest odd cycle in G, thereby extending a result of Albertson, Catlin, and Gibbons. Our class of graphs is characterized by the following property: For each odd subdivision G′ of G there exists a homomorphic map from V(G′) to V(C), where C′ is the shortest odd cycle of G′. 相似文献
17.
Marcin Kamiński Daniël Paulusma Dimitrios M. Thilikos 《Journal of Discrete Algorithms》2011,9(3):299-306
For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H∈C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class C is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H∈C if and only if there exists a constant cH such that if the treewidth of a graph is at least cH, it contains H as a contraction. We also provide a characterization of C in terms of minimal forbidden contractions. 相似文献
18.
Edward R. Scheinerman 《Journal of Graph Theory》1988,12(3):311-316
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). 相似文献
19.
Marisa Gutierrez 《Graphs and Combinatorics》2001,17(2):237-244
Let P be a class of finite families of finite sets that satisfy a property P. We call ΩP the class of intersection graphs of families in P and CliqueP the class of graphs whose family of cliques is in P. We prove that a graph G is in ΩP if and only if there is a family of complete sets of G which covers all edges of G and whose dual family is in P. This result generalizes that of Gavril for circular-arc graphs and conduces those of Fulkerson-Gross, Gavril and Monma-Wei
for interval graphs, chordal graphs, UV, DV and RDV graphs. Moreover, it leads to the characterization of Helly-graphs and dually chordal graphs as classes of intersection graphs.
We prove that if P is closed under reductions, then CliqueP=Ω(P
*∩H) (P
*= Class of dual families of families in P). We find sufficient conditions for the Clique Operator, K, to map ΩP into ΩP
*. These results generalize several known results for particular classes of intersection graphs. Furthermore, they lead to
the Roberts-Spencer characterization for the image of K and the Bandelt-Prisner result on K-fixed classes.
Received: August 18, 1997 Final version received: March 30, 1999 相似文献
20.
Tommy R. Jensen 《Discrete Mathematics》2010,310(21):3026-3029
This paper discusses an attempt at identifying a property of circuits in (nonplanar) graphs resembling the separation property of circuits in planar graphs derived from the Jordan Curve Theorem.If G is a graph and C is a circuit in G, we say that two circuits in G form a split of C if the symmetric difference of their edges sets is equal to the edge set of C, and if they are separated in G by the intersection of their vertex sets.García Moreno and Jensen, A note on semiextensions of stable circuits, Discrete Math. 309 (2009) 4952-4954, asked whether such a split exists for any circuit C whenever G is 3-connected. We observe that if true, this implies a strong form of a version of the Cycle Double-Cover Conjecture suggested in the Ph.D. thesis of Luis Goddyn. The main result of the paper shows that the property holds for Hamilton circuits in cubic graphs. 相似文献