Kazutaka Ikeda, Kenjiro Ogawa, Satoshi Tagusari, Shin-ichiro Tashiro, Morimasa Tsuchiya^∗ Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan

kenjiro@obirin.ac.jp, tagusari@bunkyo.ac.jp, tashilost@yahoo.co.jp, morimasa@keyaki.cc.u-tokai.ac.jp

For a poset P = (X, ≤^P ), the strict-double-bound graph of P is the graph sDB(P) on V (sDB(P)) = X for which vertices u and v ofsDB(P) are adjacent if and only if u 6= v and there exist elements x, y ∈ X distinct from u and v such that x ≤^P u ≤^P y and x ≤^P v ≤^P y. The strict-doublebound number ζ(G) of a graph G is defined as min{ n ; sDB(P) ∼= G ∪ Kⁿ for some poset P}. We obtain an upper bound of strict-double-bound numbers of graphs with a cut-set generating a complete subgraph. We also estimate upper bounds of strict-double-bound numbers of chordal graphs.

Keywords: strict-double-bound graph, strict-double-bound number, cut-set, chordal graph

Mathematics Subject Classification : 05C62, 05C76

DOI: 10.5614/ejgta.2021.9.2.16

1. Introduction

In this paper we consider finite graphs with no loops and no multiple edges, and finite posets. For a graph G and S ⊆ V (G), hSi^V is the induced subgraph on S and G − S = hV (G) − Si^V . The graph Kⁿ is a graph with n vertices and no edges.

A clique in a graph G is the vertex set of a maximal complete subgraph of G. A family Q = {Q1, Q2, . . . , Qm} is an edge clique cover of G if each Qⁱ is a clique of G and for each uv ∈ E(G), there exists Qⁱ ∈ Q such that u, v ∈ Qⁱ .

Received: 23 February 2019, Revised: 22 March 2021, Accepted: 24 April 2021.

^* corresponding author

A partially ordered set (poset) P = (X, ≤^P ) consists of a non-empty set X and a binary relation ≤^P on X which satisfy reflexive law, anti-symmetric law and transitive law:

• 1. For all u ∈ X, u ≤^P u : reflexive law.
• 2. If u ≤^P v and v ≤^P u, then u = v : anti-symmetric law.
• 3. If u ≤^P v and v ≤^P w, then u ≤^P w : transitive law.

For u, v ∈ P, u and v are comparable if u ≤^P v or v ≤^P u, and otherwise u and v are incomparable.

For a poset P, let Max(P) be the set of all maximal elements of P and Min(P) be the set of all minimal elements of P. For a poset P and an element v ∈ V (P), U^P (v) = {u ∈ V (P); v ≤^P u} and L^P (v) = {u ∈ V (P); u ≤^P v}. For a poset P and elements u and v of P, u k v denotes that u is incomparable with v in P.

McMorris and Zaslavsky [6] introduced concepts of some kinds of graphs on posets, that is, upper bound graphs, strict upper bound graphs, double bound graphs and strict-double-bound graphs. Langley et. al [4] and Scott [10] dealt with interval strict upper bound graphs and chordal strict upper bound graphs. Cheston and Jap [1] studied upper bound graphs from the viewpoint of algorithms.

We consider strict-double-bound graphs and strict-double-bound numbers. For a poset P = (X, ≤^P ), the strict-double-bound graph (sDB-graph) of P is the graph sDB(P) on V (sDB(P)) = X for which vertices u and v of sDB(P) are adjacent if and only if u 6= v and there exist elements x, y ∈ X distinct from u and v such that x ≤^P u ≤^P y and x ≤^P v ≤^P y. We say that a graph G is a strict-double-bound graph if there exists a poset whose strict-double-bound graph is isomorphic to G. Note that maximal elements and minimal elements of a poset P are isolated vertices of sDB(P). So, a connected graph with at least two vertices is not a strict-double-bound graph. Scott [11] showed the following result.

Theorem 1.1 (Scott [11]). Any graph that is the disjoint union of a non-trivial component and enough number of isolated vertices is a strict-double-bound graph.

Therefore, we introduced the strict-double-bound number of a graph in [8]. The strict-doublebound number ζ(G) of a graph G is defined as min{ n ; sDB(P) ∼= G ∪ Kⁿ for some poset P}. Scott [11] obtained the following result, using a concept of transitive double competition numbers.

Theorem 1.2 (Scott [11]). For a non-trivial connected graph G and a minimal edge clique cover Q of G, l 2 p |Q|m ≤ ζ(G) ≤ |Q| + 1.

In [7] we obtain the following result.

Proposition 1.1 (Ogawa et. al [7]). Let G be a connected graph with at least two vertices and P a poset with sDB(P) ∼= G ∪ Kζ(G) . Then | Max(P) ∪ Min(P)| = ζ(G).

By Theorem 1.2, we obtained that ζ(Kn) = 2 for n ≥ 2. We already obtained strict-doublebound numbers of K1,n, Pn, Cⁿ and Wⁿ in [3] and [8]. We also gave an upper bound of strictdouble-bound numbers of non-trivial trees in [8].

The sum G + H of two graphs G and H is the graph with the vertex set V (G + H) = V (G) ∪ V (H) and the edge set E(G + H) = E(G) ∪ E(H) ∪ {uv ; u ∈ V (G), v ∈ V (H)}. In [3] we also obtained the following result on the sum operation.

Theorem 1.3 (Konishi et. al [3]). For a graph G with at least two vertices and no isolated vertices, ζ(Kⁿ + G) = ζ(G) for n ≥ 1.

We consider another operation on graphs. The union G ∪ H of two graphs G and H is the graph with the vertex set V (G∪H) = V (G)∪V (H) and the edge set E(G∪H) = E(G)∪E(H). In this paper, we consider graphs with a cut-set generating a complete graph. Using concepts of cut-sets and union of graphs, we estimate a strict-double-bound number of a graph.

2. Cut-vertices and strict-double-bound numbers

In this section we consider connected graphs and cut-vertices. We obtain the following result. For a graph G, k(G) is the number of connected components. For a graph G, a vertex v of G is called a cut-vertex if k(G − v) > k(G).

Theorem 2.1. Let G be a connected graph with a cut-vertex s and G − s has two components G¹ and G2. For i = 1, 2, let Hⁱ = hV (Gi) ∪ {s}i^V and P(Hi) be a poset such that sDB(P(Hi)) ∼= Hⁱ ∪ Kζ(Hi) . Then ζ(G) ≤ ζ(H1) + ζ(H2) − 1.

Proof. For i = 1, 2, let αⁱ be a minimal element of P(Hi) such that αⁱ ≤P(Hi) s. We construct a poset Q as follows:

• 1. V (Q) = V (P(H1)) ∪ V (P(H2)) − {α2},
• 2. x ≤^Q x for all x ∈ V (Q),
• 3. for x ∈ Min(P(H1)) ∪ (Min(P(H2)) − {α2}) and y ∈ V (Q), x ≤^Q y if x ≤P(Hi) y,
• 4. for x ∈ V (Q) and y ∈ Max(P(H1)) ∪ Max(P(H2)), x ≤^Q y if x ≤P(Hi) y,
• 5. for x ∈ V (Q) − (Max(P(H1)) ∪ Min(P(H1)) ∪ Max(P(H2)) ∪ Min(P(H2))) and γ ∈ Max(P(H2)), α¹ ≤^Q x ≤^Q γ and α¹ ≤^Q γ if α² ≤P(H2) x ≤P(H2) γ.

Note that H¹ ∪ H² = G. We show that sDB(Q) ∼= G ∪ Km, where m = ζ(H1) + ζ(H2) − 1. We consider the following cases.

Case 1. u, v ∈ V (P(Hi)) − (Max(P(Hi)) ∪ Min(P(Hi))) and uv ∈ E(Hi) (i = 1, 2) Then there exist a ∈ Min(P(Hi)) and b ∈ Max(P(Hi)) ⊆ Max(Q) such that a ≤P(Hi) u ≤P(Hi) b and a ≤P(Hi) v ≤P(Hi) b.

Subcase 1.1. a 6= α²

Then a ∈ Min(Q). So a ≤^Q u ≤^Q b and a ≤^Q v ≤^Q b. And uv ∈ E(sDB(Q)).

Subcase 1.2. a = α²

Then α¹ ≤^Q u ≤^Q b and α¹ ≤^Q v ≤^Q b. And uv ∈ E(sDB(Q)). Case 2. u, v ∈ V (P(Hi)) − (Max(P(Hi)) ∪ Min(P(Hi))) and uv /∈ E(Hi) (i = 1, 2)

If \(L_{P(H_2)}(u) \cap L_{P(H_2)}(v) = \emptyset\) for \(u, v \in V(P(H_2))\), then \(\alpha_2 \notin L_{P(H_2)}(u) \cap L_{P(H_2)}(v)\) and \(L_Q(u) \cap L_Q(v) = \emptyset\). Thus for \(uv \notin E(H_i)\), \(L_Q(u) \cap L_Q(v) = \emptyset\) or \(U_Q(u) \cap U_Q(v) = \emptyset\). So \(uv \notin E(\mathrm{sDB}(Q))\).

Case 3. \(u \in V(P(H_1)) - (\text{Max}(P(H_1)) \cup \text{Min}(P(H_1)))\) and \(v \in V(P(H_2)) - (\text{Max}(P(H_2)) \cup \text{Min}(P(H_2)))\)

Then \(U_Q(u) \subseteq U_{P(H_1)}(u)\), \(U_Q(v) \subseteq U_{P(H_2)}(v)\) and \(U_{P(H_1)}(u) \cap U_{P(H_2)}(v) = \emptyset\). Thus \(U_Q(u) \cap U_Q(v) = \emptyset\) and \(uv \notin E(\mathrm{sDB}(Q))\).

Therefore \(\mathrm{sDB}(Q) \cong G \cup \overline{K}_m\), where \(m = \zeta(H_1) + \zeta(H_2) - 1\).

3. Cut-sets and strict-double-bound numbers

In this section we consider connected graphs and cut-sets inducing complete subgraphs. For a graph G, a vertex subset S of V(G) is called a cut-set if k(G-S)>k(G). For a poset P and \(S\subseteq V(P)\), \(\operatorname{Max}(P;S)=(\bigcup_{v\in S}U_P(v))\cap\operatorname{Max}(P)\), \(\operatorname{Min}(P;S)=(\bigcup_{v\in S}L_P(v))\cap\operatorname{Min}(P)\) and \(\operatorname{NoMin}(P;S)=\{c\in\operatorname{Min}(P)\ ;\ c\parallel v \text{ for all } v\in S\}\). Then \(\operatorname{NoMin}(P;S)=\operatorname{Min}(P)-\operatorname{Min}(P;S)\).

We obtain the following result.

Theorem 3.1. Let G be a connected graph with a cut-set S, where the induced subgraph \(\langle S \rangle_V\) is a complete subgraph and G - S has components \(G_1, G_2, \ldots, G_k\). For \(i = 1, 2, \ldots, k\), let \(H_i = \langle V(G_i) \cup S \rangle_V\) and \(P(H_i)\) be a poset such that \(\mathrm{sDB}(P(H_i)) \cong H_i \cup \overline{K}_{\zeta(H_i)}\). Then \(\zeta(G) \leq \sum_{i=1}^k |\operatorname{Max}(P(H_i))| + \operatorname{max}\{|\operatorname{Min}(P(H_i); S)| ; i = 1, 2, \ldots, k\} + \operatorname{max}\{|\operatorname{NoMin}(P(H_i); S)| ; i = 1, 2, \ldots, k\}\).

Proof. For \(i=1,2,\ldots,k\), let \(\operatorname{Min}(P(H_i);S)=\{\alpha_{i,1},\alpha_{i,2},\ldots,\alpha_{i,p_i}\}\) and \(\operatorname{NoMin}(P(H_i);S)=\{\beta_{i,1},\beta_{i,2},\ldots,\beta_{i,q_i}\}\). We assume that for \(i=1,2,\ldots,k, |\operatorname{Min}(P(H_1);S)| \geq |\operatorname{Min}(P(H_i);S)|\) and \(|\operatorname{NoMin}(P(H_i);S)| \geq |\operatorname{NoMin}(P(H_i);S)|\). We construct a poset Q as follows:

• 1. \(V(Q) = \bigcup_{i=1}^{k} V(P(H_i)) \bigcup_{i \neq 1} \min(P(H_i); S) \bigcup_{i \neq t} \operatorname{NoMin}(P(H_i); S)\)= \((\bigcup_{i=1}^{k} (\operatorname{Max}(P(H_i)) \cup V(H_i))) \cup \operatorname{Min}(P(H_1); S) \cup \operatorname{NoMin}(P(H_t); S),\)
• 2. \(x \leq_Q x\) for all \(x \in V(Q)\),
• 3. for \(x \in Min(P(H_1); S) \cup NoMin(P(H_t); S)\) and \(y \in V(Q)\), \(x \leq_Q y\) if \(x \leq_{P(H_i)} y\),
• 4. for \(x \in V(Q)\) and \(y \in \bigcup_{i=1}^k \operatorname{Max}(P(H_i)), x \leq_Q y\) if \(x \leq_{P(H_i)} y\),
• 5. for \(i=1,2,\ldots,k\), if \(w\in V(P(H_i))-(\operatorname{Max}(P(H_i))\cup\operatorname{Min}(P(H_i)))\), \(\alpha_{i,j}\in\operatorname{Min}(P(H_i);S)\), \(\gamma\in\operatorname{Max}(P(H_i))\) and \(\alpha_{i,j}\leq_{P(H_i)}w\leq_{P(H_i)}\gamma\), then \(\alpha_{1,j}\leq_{Q}w\leq_{Q}\gamma\) and \(\alpha_{1,j}\leq_{Q}\gamma\),
• 6. for \(i=1,2,\ldots,k\), if \(w\in V(P(H_i))-(\operatorname{Max}(P(H_i))\cup\operatorname{Min}(P(H_i)))\), \(\beta_{i,j}\in\operatorname{NoMin}(P(H_i);S)\), \(\gamma\in\operatorname{Max}(P(H_i))\) and \(\beta_{i,j}\leq_{P(H_i)}w\leq_{P(H_i)}\gamma\), then \(\beta_{t,j}\leq_{Q}w\leq_{Q}\gamma\) and \(\beta_{t,j}\leq_{Q}\gamma\).

Note that \(H_1 \cup H_2 \cup ... \cup H_k = G\). We show that \(sDB(Q) \cong G \cup \overline{K}_m\), where \(m = (\sum_{i=1}^k |\operatorname{Max}(P(H_i))|) + |\operatorname{Min}(P(H_1); S)| + |\operatorname{NoMin}(P(H_t); S)|\). We consider the following cases.

Case 1. \(u, v \in V(P(H_1)) - (\operatorname{Max}(P(H_1)) \cup \operatorname{Min}(P(H_1)))\) and \(uv \in E(H_1)\)Then there exist \(a \in \operatorname{Min}(P(H_1))\) and \(b \in \operatorname{Max}(P(H_1)) \subseteq \operatorname{Max}(Q)\) such that \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

b and \(a \leq_{P(H_1)} v \leq_{P(H_1)} b\).

Subcase 1.1. a ∈ Min(P(H1); S)

Then a ∈ Min(Q). So a ≤^Q u ≤^Q b and a ≤^Q v ≤^Q b. And uv ∈ E(sDB(Q)).

Subcase 1.2. a ∈ NoMin(P(H1); S) Then a = β1,j . So βt,j ≤^Q u ≤^Q b and βt,j ≤^Q v ≤^Q b. And uv ∈ E(sDB(Q)).

Case 2. u, v ∈ V (P(Ht)) − (Max(P(Ht)) ∪ Min(P(Ht))) and uv ∈ E(Ht)

Then there exist a ∈ Min(P(Ht)) and b ∈ Max(P(Ht)) ⊆ Max(Q) such that a ≤P(Ht) u ≤P(Ht) b and a ≤P(Ht) v ≤P(Ht) b.

Subcase 2.1. a ∈ Min(P(Ht); S)

Then a = αt,j . So α1,j ≤^Q u ≤^Q b and α1,j ≤^Q v ≤^Q b. And uv ∈ E(sDB(Q)).

Subcase 2.2. a ∈ NoMin(P(Ht); S)

Then a ∈ Min(Q). So a ≤^Q u ≤^Q b and a ≤^Q v ≤^Q b. And uv ∈ E(sDB(Q)).

Case 3. u, v ∈ V (P(Hi)) − (Max(P(Hi)) ∪ Min(P(Hi))), uv ∈ E(Hi) and i 6= 1, t

Then there exist a ∈ Min(P(Hi)) and b ∈ Max(P(Hi)) ⊆ Max(Q) such that a ≤P(Hi) u ≤P(Hi) b and a ≤P(Hi) v ≤P(Hi) b.

Subcase 3.1. a ∈ Min(P(Hi); S)

Then a = αi,j . So α1,j ≤^Q u ≤^Q b and α1,j ≤^Q v ≤^Q b. And uv ∈ E(sDB(Q)).

Subcase 3.2. a ∈ NoMin(P(Hi); S)

Then a = βi,j . So βt,j ≤^Q u ≤^Q b and βt,j ≤^Q v ≤^Q b. And uv ∈ E(sDB(Q)).

Case 4. u, v ∈ V (P(Hi)) − (Max(P(Hi)) ∪ Min(P(Hi))) and uv /∈ E(Hi)

Then LP(Hi)(u) ∩ Min(P(Hi)) = {αi,l¹ , αi,l² , . . . , αi,l^s } ∪ {βi,f¹ , βi,f² , . . . , βi,f^d } and LP(Hi)(v) ∩ Min(P(Hi)) = {αi,g¹ , αi,g² , . . . , αi,g^o } ∪ {βi,h¹ , βi,h² , . . . , βi,h^r }. Thus LQ(u) = {α1,l¹ , α1,l² , . . . , α1,l^s } ∪ {βt,f¹ , βt,f² , . . . , βt,f^d } and LQ(v) = {α1,g¹ , α1,g² , . . . , α1,g^o } ∪ {βt,h¹ , βt,h² , . . . , βt,h^r }. Since uv /∈ E(Hi), LP(Hi)(u) ∩ LP(Hi)(v) = ∅ or UP(Hi)(u) ∩ UP(Hi)(v) = ∅. So LQ(u) ∩ LQ(v) = ∅ or UQ(u) ∩ UQ(v) = ∅. Thus uv /∈ E(sDB(Q)).

Case 5. u ∈ V (P(Hi))−(Max(P(Hi))∪Min(P(Hi))∪S), v ∈ V (P(H^j ))−(Max(P(H^j ))∪ Min(P(H^j )) ∪ S) and i 6= j

Then UQ(u) ⊆ UP(Hi)(u), UQ(v) ⊆ UP(H^j )(v) and UP(Hi)(u) ∩ UP(H^j )(v) = ∅. Thus UQ(u) ∩ UQ(v) = ∅ and uv /∈ E(sDB(Q)).

Case 6. u, v ∈ S

Since S ⊆ V (P(H1)) − (Max(P(H1)) ∪ Min(P(H1))) and uv ∈ E(H1), uv ∈ E(sDB(Q)) by Case 1.

Thus sDB(Q) ∼= G ∪ Km, where m = P^{k i}=1 | Max(P(Hi))| + | Min(P(H1); S)| + | NoMin( P(Ht); S)|. Therefore ζ(G) ≤ P^{k i}=1 | Max(P(Hi))| + | Min(P(H1); S)| + | NoMin(P(Ht); S)| = P^{k i}=1 | Max(P(Hi))| + maxi=1,2,...,k | Min(P(Hi); S)| + maxi=1,2,...,k | NoMin(P(Hi); S)|.

4. Chordal graphs

A graph is called a chordal graph if every cycle of length greater than 3 has a chord. We already know the following result in [2].

Theorem 4.1. For a graph G, G is a chordal graph if and only if every minimal cut-set induces a complete subgraph of G.

Since a minimal cut-set of a chordal graph generates a complete subgraph, we have the following result on chordal graphs by Theorem 3.1.

Proposition 4.1. Let G be a connected chordal graph.

• (1) If G is a complete graph, then \(\zeta(G) = 2\).
• (2) If G is a non-complete graph, then \(\zeta(G) \leq \sum_{i=1}^{k} |\operatorname{Max}(P(H_i))| + \operatorname{max}\{ |\operatorname{Min}(P(H_i); S)| ; i = 1, 2, \ldots, k\} + \operatorname{max}\{ |\operatorname{NoMin}(P(H_i); S)| ; i = 1, 2, \ldots, k\}, where <math>S \subseteq V(G)\) is a minimal cut-set, \(G_1, G_2, \ldots, G_k\) are components of G S, \(H_i = \langle V(G_i) \cup S \rangle_V\) for \(i = 1, 2, \ldots, k\) and \(P(H_i)\) is a poset such that \(\operatorname{sDB}(P(H_i)) \cong H_i \cup \overline{K}_{\zeta(H_i)}\) for \(i = 1, 2, \ldots, k\).

5. k-trees

In this section we consider k-trees. A k-tree is a chordal graph that can be constructed from a complete graph \(K_k\) by a sequence of vertex additions in which the neighborhood of each new vertex is a complete subgraph with k vertices of the current graph. Further k-trees other than complete graphs are called non-clique k-trees. And k-trees are connected graphs. In [5] and [9] Lin et. all reported some properties of k-trees.

Let \(G(K_k; v_1, v_2, \ldots, v_m)\) be a k-tree with the vertex additions sequence \(v_1, v_2, \ldots, v_m\). Let \(P_Z\) be a poset with \(V(P_Z) = \{z_1, u_0, u_1, \ldots, u_k, z_2\}\), \(z_1 \leq_{P_Z} u_j \leq_{P_Z} z_2\), \(z_1 \leq_{P_Z} z_2\), \(z_1 \leq_{P_Z} z_1\), \(u_j \leq_{P_Z} u_j\) and \(z_2 \leq_{P_Z} z_2\) for \(j = 0, 1, \ldots, k\). Then \(\mathrm{sDB}(P_Z) \cong K_{k+1} \cup \overline{K}_2\). We obtain the following result by Theorem 3.1.

Proposition 5.1. Let \(G(K_k; v_1, v_2, \dots, v_m)\) be a k-tree with the vertex addition sequence \(v_1, v_2, \dots, v_m\). Then \(\zeta(G(K_k; v_1, v_2, \dots, v_m)) \leq m+1\).

Proof. The proof is by induction on the length of a vertex addition sequence. Since \(G(K_k; v_1) \cong K_{k+1}\), \(\zeta(G(K_k; v_1)) = \zeta(K_{k+1}) = 2 \le 1+1\). By induction hypothesis, \(\zeta(G(K_k; v_1, v_2, \ldots, v_{m-1})) \le m\). Let P be a poset such that \(\mathrm{sDB}(P) \cong G(K_k; v_1, v_2, \ldots, v_{m-1}) \cup \overline{K}_n\), where \(n = \zeta(G(K_k; v_1, v_2, \ldots, v_{m-1})) \le m\). Let P be the neighborhood of P of P of P of P of P and P is a cut-set of P of P of P and P is a cut-set of P of P of P and P is a cut-set of P of P of P of P and P is a cut-set of P of P of P of P and P is a cut-set of P of P of P of P of P of P of P and P is a cut-set of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of P of

References

• [1] G.A. Cheston and T.S. Jap, A survey of the algorithmic properties of simplicial, upper bound and middle graphs, J. Graph Algorithms Appl. 10 (2006), 159–190.
• [2] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980
• [3] S. Konishi, K. Ogawa, S. Tagusari, and M. Tsuchiya, Note on strict-double-bound numbers of paths, cycles, and wheels, J. Combin. Math. Combin. Comput. 83 (2012), 205–210.

• [4] L. Langley, S.K. Merz, J.R. Lundgren, and C.W. Rasmussen, Posets with interval or chordal strict upper and lower bound graphs, Congr. Numer. 125 (1997), 153–160.
• [5] I.-J. Lin, T.A. McKee, and D.B. West, The leafage of a chordal graph, Discuss. Math. Graph Theory 18 (1998), 23–48.
• [6] F.R. McMorris and T. Zaslavsky, Bound graphs of a partially ordered set, J. Comb. Inf. Syst. Sci. 7 (1982), 134–138.
• [7] K. Ogawa, K. Shiraki, S. Tagusari, and M. Tsuchiya, On strict-double-bound numbers of complete pseudo-regular trees, Far East Journal of Applied Mathematics 93 (2015), 1–19.
• [8] K. Ogawa, S. Tagusari, and M. Tsuchiya, Note on strict-double-bound graphs and numbers, AKCE Int. J. Graphs Comb. 11 (2014),127–132.
• [9] D.J. Rose, Triangulated graphs and the elimination process, Journal of Mathematical Analysis and Applications 32 (1970), 597–609.
• [10] D.D. Scott, Posets with interval upper bound graphs, Order 3 (1986), 269–281.
• [11] D.D. Scott, The competition-common enemy graph of a digraph, Discrete Appl. Math. 17 (1987), 269–280.