共查询到20条相似文献,搜索用时 0 毫秒
1.
Juhani Nieminen 《Journal of Geometry》1989,34(1-2):146-151
A join space is an abstract model for partially ordered linear, spherical and projective geometries. A characterization for chordal graphs which are join spaces is given: a chordal graph is a join space if and only if it does not contain one of the two forbidden graphs as an induced subgraph. 相似文献
2.
Vincent Bouchitté 《Order》1985,2(2):119-122
We prove that a bipartite graph is chordal if and only if it has an elimination scheme. This leads to a polynomial algorithm to recognize whether an ordered set is cycle-free. 相似文献
3.
Guoli Ding 《Journal of Graph Theory》1998,28(2):105-114
Let precedes, equal to be the induced-minor relation. It is shown that, for every t, all chordal graphs of clique number at most t are well-quasi-ordered by precedes, equal to. On the other hand, if the bound on clique number is dropped, even the class of interval graphs is not well-quasi-ordered by precedes, equal to. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 105–114, 1998 相似文献
4.
R. Sritharan 《Discrete Mathematics》2008,308(12):2581-2588
Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete. 相似文献
5.
《Discrete Mathematics》2007,307(17-18):2309-2314
6.
A function diagram (f-diagram) D consists of the family of curves {ñ} obtained from n continuous functions . We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the fi are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of . Computational complexity results are obtained for recognizing such graphs. 相似文献
7.
Given a set R of affine subspaces in Rd of dimension e, its intersection graph G has a vertex for each subspace, and two vertices are adjacent in G if and only if their corresponding subspaces intersect. For each pair of positive integers d and e we obtain the class of (d,e)-subspace intersection graphs. We classify the classes of (d,e)-subspace intersection graphs by containment, for e=1 or e=d−1 or d≤4. 相似文献
8.
A graphG = (V, E) is a modular intersection graph on a finite setU if there is a family of subsetsS = {S
xx V} ofU and positive integerst < m such thatxy is an edge ofG if and only if |S
x Sy| (modm) t. Modular representations of various classes of graphs and studied as well as some related parameters.Research supported by Grant N00014-89-J-1643 from the Office of Naval Research. 相似文献
9.
10.
11.
Let W 1,??,W n be independent random subsets of [m]={1,??,m}. Assuming that each W i is uniformly distributed in the class of d-subsets of?[m] we study the uniform random intersection graph G s (n,m,d) on the vertex set {W 1,??W n }, defined by the adjacency relation: W i ??W j whenever |W i ??W j |?Rs. For even?n we show that as n,m???? the edge density threshold for the property that G s (n,m,d) contains a perfect matching is asymptotically the same as that for G s (n,m,d) being connected. 相似文献
12.
We describe a method of computing equivariant and ordinary intersection cohomology of certain varieties with actions of algebraic
tori, in terms of structure of the zero- and one-dimensional orbits. The class of varieties to which our formula applies includes
Schubert varieties in flag varieties and affine flag varieties. We also prove a monotonicity result on local intersection
cohomology stalks.
Received: 9 November 2000 / Published online: 24 September 2001 相似文献
13.
In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph G and k≥0, the intersection graph Qk(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices Hx and Hy in Qk(G) are adjacent whenever the intersection Hx∩Hy contains a subgraph isomorphic to Qk. Characterizations of clique-graphs in terms of these intersection concepts when k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph G, denoted , whose vertices are maximal hypercubes of G, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph H is diamond-free if and only if there exists a median graph G such that H is isomorphic to . We also study convergence of median graphs to the one-vertex graph with respect to all these operations. 相似文献
14.
In this paper, general results are presented that are related to ?-tolerance intersection graphs previously defined by Jacobson, McMorris, and Mulder. For example, it is shown that all graphs are ?-tolerance intersection graphs for all ?, yet for “nice” ?, almost no graphs are ?-tolerance interval graphs. Additional results about representation of trees are given. 相似文献
15.
16.
Selçuk Kayacan 《代数通讯》2018,46(4):1492-1505
The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper, we classify finite solvable groups whose intersection graphs are not 2-connected and finite nilpotent groups whose intersection graphs are not 3-connected. Our methods are elementary. 相似文献
17.
Paul J. Tanenbaum 《Journal of Graph Theory》1999,32(2):171-190
We characterize the pairs (G1, G2) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G1 is the intersection graph of the subsets and G2 is the intersection graph of their complements. We also consider several special cases and explore bounds on the size of the universal set. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 171–190, 1999 相似文献
18.
We study the graphs G for which their toric ideals I G are complete intersections. In particular, we prove that for a connected graph G such that I G is a complete intersection all of its blocks are bipartite except for at most two. We prove that toric ideals of graphs which are complete intersections are circuit ideals. In this case, the generators of the toric ideal correspond to even cycles of G except of at most one generator, which corresponds to two edge disjoint odd cycles joint at a vertex or with a path. We prove that the blocks of these graphs satisfy the odd cycle condition. Finally, we characterize all complete intersection toric ideals of graphs which are normal. 相似文献
19.
Robert E. Jamison characterized chordal graphs by the edge set of every k-cycle being the symmetric difference of k−2 triangles. Strongly chordal (and chordal bipartite) graphs can be similarly characterized in terms of the distribution of triangles (respectively, quadrilaterals). These results motivate a definition of ‘strongly chordal bipartite graphs’, forming a class intermediate between bipartite interval graphs and chordal bipartite graphs. 相似文献
20.
We give a tight bound for the triple intersection numbers of Paley graphs. In particular, we show that any three vertices have a common neighbor in Paley graphs of order larger than 25. 相似文献