共查询到20条相似文献,搜索用时 15 毫秒
1.
Cover-Incomparability Graphs of Posets 总被引:1,自引:1,他引:0
Boštjan Brešar Manoj Changat Sandi Klavžar Matjaž Kovše Joseph Mathews Antony Mathews 《Order》2008,25(4):335-347
Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability
and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized
in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems
are also stated. 相似文献
2.
We investigate the class of intersection graphs of paths on a grid (VPG graphs), and specifically the relationship between the bending number of a cocomparability graph and the poset dimension of its complement. We show that the bending number of a cocomparability graph G is at most the poset dimension of the complement of G minus one. Then, via Ramsey type arguments, we show our upper bound is best possible. 相似文献
3.
We prove two theorems concerning incidence posets of graphs, cover graphs of posets and a related graph parameter. First, answering a question of Haxell, we show that the chromatic number of a graph is not bounded in terms of the dimension of its incidence poset, provided the dimension is at least four. Second, answering a question of K?í? and Ne?et?il, we show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most two. 相似文献
4.
Bill Sands 《Order》2010,27(1):1-8
A finite poset F has the maximal antichain property if every maximal F-free subposet of every finite poset P contains a maximal antichain of P. We find all finite posets with the maximal antichain property. 相似文献
5.
We show that there are four infinite prime graphs such that every infinite prime graph with no infinite clique embeds one
of these graphs. We derive a similar result for infinite prime posets with no infinite chain or no infinite antichain. 相似文献
6.
偏序集上的滤子极大理想 总被引:3,自引:1,他引:2
在偏序集上引入并考察了滤子极大理想的概念,证明了相应的存在性定理。引入并考察了伪极大元和伪既约元的概念,利用图表的形式对连续格中各种类型的既约元和素元之间的关系进行了归纳总结,完善了文献《Continuous Lattices and Domains》(作者:G.Gierz,et al)中的一个图表的相关内容,填补了在分配的连续格情形该图表的一个未知内容,部分地回答了该文献中的一个问题。 相似文献
7.
如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I,都有G-I有完美匹配,则称G是独立集可削去的因子临界图.如果图G不是独立集可削去的因子临界图,而对任意两个小相邻的顶点x与y,G xy足独立集可削去的因子临界图,则称G足极大非独立集可削去的因子临界图,本刻画了极大非独立集可削去的因子临界图。 相似文献
8.
A topology on the vertex set of a comparability graph G is said to be compatible (respectively, weakly compatible) with G if each induced subgraph (respectively, each finite induced subgraph) is topologically connected if and only it it is graph-connected; a weakly compatible topology on the vertex set of a graph completely determines the graph structure. We consider here the problem of deciding whether or not a comparability graph has a compact compatible or weakly compatible topology and in the case of graphs with small cycles, hence in the case of trees, we give a characterization. 相似文献
9.
In this paper we show that the recognition problem for C-I graphs of posets is NP-complete. On the other hand, we prove that
induced subgraphs of C-I graphs are exactly complements of comparability graphs, and hence the recognition problem for induced
subgraphs of C-I graphs of posets is polynomial. 相似文献
10.
11.
12.
13.
Maximal Energy Bipartite Graphs 总被引:1,自引:0,他引:1
Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then
must hold, characterize those bipartite graphs for which this bound is sharp, and provide an infinite family of maximal energy
bipartite graphs.
Received: December 1, 2000 Final version received: August 28, 2001
RID="*"
ID="*" The author thanks the Swedish Natural Science Research Council (NFR) – grant M12342-300 – for its support.
Acknowledgments. The authors would like to thank Ivan Gutman for encouraging them to write this paper, and for helpful discussions on this
topic. They also would like to thank Edwin van Dam for his reference concerning connected bipartite regular graphs with four
eigenvalues. 相似文献
14.
In this paper we present an efficient algorithm for generating maximal triangle-free graphs. A program based on this algorithm has been used to check a conjecture of Erdo´´s about the local density of triangle-free graphs and turned out to be very powerful for the computation of triangle Ramsey numbers. 相似文献
15.
Jens Gustedt 《Order》1998,15(3):203-220
We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it.In particular we show that the following classes have infinite antichains with respect to the induced subgraph/poset relation: interval graphs and orders, N-free orders, orders with bounded decomposition width. On the other hand for orders with bounded decomposition diameter finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties. 相似文献
16.
17.
18.
In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276. 相似文献
19.
For a finite poset P = (V, ≤ ), let _s(P){\cal B}_s(P) consist of all triples (x,y,z) ∈ V
3 such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = (V,E), let Bs(G){\cal B}_s(G) consist of all triples (x,y,z) ∈ V
3 such that y is an internal vertex on an induced path in G between x and z. The ternary relations Bs(P){\cal B}_s(P) and Bs(G){\cal B}_s(G) are well-known examples of so-called strict betweennesses. We characterize the pairs (P,G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation Bs(P)=Bs(G){\cal B}_s(P)={\cal B}_s(G). 相似文献
20.
Spectral Integral Variations of Degree Maximal Graphs 总被引:3,自引:0,他引:3
Fan Yizheng 《Linear and Multilinear Algebra》2003,51(2):147-154
The concept of the spectral integral variation was introduced by Fan [Fan Yizheng (2002). On spectral integral variations of graphs. Linear and Multilinear Algebra , 50 , 133-142] to study the general graphs with all changed eigenvalues moving up by integers when an edge is added. Here we consider the spectral integral variations of maximal graphs G , and successfully give an equivalent condition for the spectral integral variation of G occurring in two places by adding an edge e . We also characterize whether the graph G + e is maximal so that an explicit interpretation of the above condition is obtained, where G + e denotes the graph obtained from G by adding an edge e . 相似文献