×

On upper bound graphs whose complements are also upper bound graphs. (English) Zbl 0906.05034

Authors’ summary: We consider upper bound graphs and double bound graphs of posets. We obtain a characterization of upper bound graphs whose complements are also upper bound graphs as follows: for a connected graph \(G\), both \(G\) and \(\overline G\) are upper bound graphs if and only if \(G\) is a split graph with \(V(G)= K+ S\), where \(K\) is a clique and \(S\) is an independent set, satisfying one of the following conditions: (1) there exists a vertex in \(K\) with no neighbour in \(S\), or (2) for each edge \(e= uv\) in \(K\), there exists a vertex \(w\in S\) such that \(u,v\in N(w)\), and for each pair of vertices \(x,y\in S\), there exists a vertex \(v\in K\) such that neither \(x\) nor \(y\) is adjacent to \(v\). We also obtain some properties of double bound graphs of height one posets.

MSC:

05C35 Extremal problems in graph theory
05C75 Structural characterization of families of graphs
Full Text: DOI

References:

[1] Diny, D., The double bound graph of a partially ordered set, J. Combin., Inform. System Sci., 10, 52-56 (1985) · Zbl 0635.05045
[2] Era, H.; Tsuchiya, M., On double bound graphs whose complements are also double bound graphs, (Proc. Schl. Sci. Tokai Univ., 31 (1996)), 25-29 · Zbl 0852.05073
[3] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic press: Academic press New York · Zbl 0541.05054
[4] McMorris, F. R.; Zaslavsky, T., Bound graphs of a partially orders set, J. Combin., Inform. System Sci., 7, 134-138 (1982) · Zbl 0525.05060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.