Note on strict-double-bound numbers of nearly complete graphs missing some edges

作者：Ogawa Kenjiro; Soejima Ryoko; Tagusari Satoshi; Tsuchiya Morimasa^*

来源：Discrete Mathematics, 2012, 312(3): 584-587.

DOI：10.1016/j.disc.2011.04.021

• Strict-double-bound graph
• Strict-double-bound number
• Nearly complete graph missing edges

For a poset P = (X, %26lt;=(p)), the strict-double-bound graph (strict DB-graph sDB(P)) is the graph on X for which u is adjacent to v if and only if u not equal v and there exist elements x. y epsilon X distinct from u and v such that x %26lt;= u %26lt;= y and x %26lt;= v %26lt;= y. The strict-double-bound number zeta(G) of a graph G is defined as mini{l; sDB(P) congruent to G boolean OR K-f for some poset P}. %26lt;br%26gt;We obtain strict-double-bound numbers of nearly complete graphs missing one, two or three edges. In particular, we prove that zeta (K-n - e) = 3, zeta(K-n -E(P-3)) = 3, zeta (K-n - E(2K(2))) = 4, zeta(K-n - E(K-3)) = 4, zeta(K-n - E(P-4)) = 4, E(K-1.3)) = 3, zeta(K-n - E(P-3 boolean OR K-2)) = 4 and zeta(K-3 - E(3K(2))) = 5.

• 出版日期2012-2-6