# Some New Classes of Open Distance-Pattern Uniform Graphs

Authors: Bibin K. Jose
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

Given an arbitrary nonempty subsetM of vertices in a graph G=(V,E), each vertex u in G is associated with the set fMo(u)={d(u,v):v∈M,u≠v} and called its open M-distance-pattern. The graph G is called open distance-pattern uniform (odpu-) graph if there exists a subset M of V(G) such that fMo(u)=fMo(v) for all u,v∈V(G), and M is called an open distance-pattern uniform (odpu-) set of G. The minimum cardinality of an odpu-set in G, if it exists, is called the odpu-number of G and is denoted by od(G). Given some property P, we establish characterization of odpu-graph with property P. In this paper, we characterize odpu-chordal graphs, and thereby characterize interval graphs, split graphs, strongly chordal graphs, maximal outerplanar graphs, and ptolemaic graphs that are odpu-graphs. We also characterize odpu-self-complementary graphs, odpu-distance-hereditary graphs, and odpu-cographs. We prove that the odpu-number of cographs is even and establish that any graph G can be embedded into a self-complementary odpu-graph H, such that G and G¯ are induced subgraphs of H. We also prove that the odpu-number of a maximal outerplanar graph is either 2 or 5.


---

## Body

## 1. Introduction

All graphs considered in this paper are finite, simple, undirected, and connected. For graph theoretic terminology, we refer to Harary [1].The concept of open distance-pattern and open distance-pattern uniform graphs was studied in [2]. Given an arbitrary nonempty subset M of vertices in a graph G=(V,E), the open M-distance-pattern of a vertex u in G is defined to be the set fMo(u)={d(u,v):v∈M,u≠v}, where d(x,y) denotes the distance between the vertices x and y in G. If there exists a nonempty set M⊆V(G) such that fMo(u) is independent of the choice of u, then G is called open distance-pattern uniform (odpu-) graph, and the set M is called an open distance-pattern uniform (odpu-) set. The minimum cardinality of an odpu-set in G, if it exists, is the odpu-number of G and is denoted by od(G). In this paper, we characterize several classes of odpu graph such as odpu-chordal graphs, interval graphs, split graphs, strongly chordal graphs, maximal outerplanar graphs, ptolemaic graphs, self-complementary graphs, odpu-distance-hereditary graphs, and odpu-cographs. We need the following definitions and previous results.For a vertexv in a connected graph G, the eccentricity e(v) of v is the distance to a vertex farthest from v. The minimum eccentricity among the vertices of a connected graph G is the radius of G, denoted by r(G), and the maximum eccentricity is its diameter, d(G). A vertex v in a connected graph G is called a central vertex if e(v)=r(G). The collection of all central vertices is called the center of G denoted by Z(G).In paper [2], it is proved that a graph G with radius r(G) is an odpu graph if and only if the open distance-pattern of any vertex u in G is fMo(u)={1,2,…,r(G)}, and a graph is an odpu-graph if and only if its centre Z(G) is an odpu-set, thereby characterizing odpu-graphs, which in fact suggests an easy method to check the existence of an odpu-set for a given graph. The central subgraph 〈Z(G)〉 of a graph is the subgraph induced by the center.Proposition 1 (see [2]).
For any graphG, od(G)=2 if and only if there exist at least two vertices x,y∈V(G) such that deg(x)=deg(y)=|V(G)|-1, where deg(x) denote the degree of the vertex x in G.Proposition 2 (see [2]).
There is no graph having odpu-number three.Proposition 3 (see [2]).
A graphG is an odpu graph if and only if its centre Z(G) is an odpu set, and hence |Z(G)|≥2.Proposition 4 (see [2]).
All self-centered graphs are odpu graphs.Theorem 5 (see [2]).
The shadow graph of any complete graphKn, n≥3 is an odpu-graph with odpu-number n+2 (the shadow graph S(G) of a graph G is obtained from G by adding for each vertex v of G a new vertex v′, called the shadow vertex of v, and joining v′ to all the neighbors of v in G).Theorem 6 (see [2]).
Every odpu-graphG satisfies r(G)≤d(G)≤r(G)+1, where r(G) and d(G) denote the radius and diameter of G, respectively.The complementG¯ of a graph G has the same vertices as G, and every pair of vertices are joined by an edge in G¯ if and only if they are not joined in G. A self-complementary graph G is one that is isomorphic to its complement G¯.Proposition 7 (see [3]).
LetG be a nontrivial self-complementary graph. Then (i)
G  has radius2  and diameter  2  or  3,(ii)
G  has diameter  3  if and only if it contains a dominating edge (an edge  e∈E  is said to be a dominating edge if every edge in  E∖{e}  is adjacent to  e),(iii)
the number of vertices of eccentricity  3  is never greater than the number of vertices of eccentricity  2.Cographs (or complement reducible graphs) are defined as the class of graphs formed from a single vertex under the closure of the operations of union and complement. Cographs have the following two remarkable properties. Firstly, they are exactly theP4-restricted graphs, and secondly, a cograph has a unique tree representation, called a cotree. In the cotree representation, leaves of the cotree represent vertices of the graph. Internal nodes of the cotree are labelled using 0 or 1 in such a way that (0) nodes and (1) nodes alternate along every path starting from the root which is always a (1) node. Each nonleaf vertex of T has at least two children. The root will have only one (0) node child if and only if the represented cograph is disconnected. Also, the cotree for a particular cograph is unique up to a permutation of the children of the internal nodes. Two vertices x and y of the graph are adjacent if and only if the unique path from x to the root of the tree meets the unique path from y to the root at a (1) node. In order to establish various properties about cographs, we label each internal node of a cotree as follows: the root is labelled (1), the children of a node with label (1) are labelled (0), and children of a node labelled (0) are labelled (1). Henceforth, we assume all cotrees to be labelled as such, and we will refer to the internal nodes of cotrees as (0)-nodes and (1)-nodes (cf. [4–7]).Theorem 8 (see [4]).
A graphG has a cotree if and only if G is a cograph. In that case, the cotree representation is unique.A graphG is said to be chordal if every cycle of length at least 4 has a chord, that is, an edge joining nonconsecutive vertices of the cycle. A subset S⊆V(G) is called a vertex separator of G for nonadjacent vertices a and b (or a-b separator of G) if, in G-S (the graph obtained from G by the removal of the vertices of S and incident edges), the vertices a and b belong to distinct connected components. Let S(a,b,G) be the set of all a-b separators of G. If no proper subset of S∈S(a,b,G) belongs to S(a,b,G), then S is called a minimal a-b separator of G. Let S0(a,b,G) be the set of all minimal a-b separators of G. The following propositions (cf. [8]) are needed in proving our main results.Proposition 9 (see [8]).
IfG is a chordal graph and x, y are distinct nonadjacent vertices in 〈Z(G)〉, the central graph of G, and S0∈S0(x,y,G), then the following conditions hold:(1)
S0⊆Z(G),(2)
there are at least two distinct vertices  z1,z2∈S0  such that for every  i=1,2  either  dG(x,zi)=1  or  dG(y,zi)=1. In particular,|S0|≥2.Proposition 10 (see [8]).
IfG is a chordal graph and x, y are distinct nonadjacent vertices in 〈Z(G)〉, the central subgraph of G, then S0(x,y,G)=S0(x,y,〈Z(G)〉).Proposition 11 (see [8]).
IfG is a chordal graph, then 〈Z(G)〉 is connected.Proposition 12 (see [8]).
IfG is a chordal graph, then d(〈Z(G)〉)≤3.Proposition 13 (see [8]).
IfG is a chordal graph with (r,d)=(2,3), then d(〈Z(G)〉)≤2.Proposition 14 (see [8]).
There are no self-centered chordal graphG with (r,d)=(3,3). Consequently, for a self-centered chordal graph G, r(G)≤2.A distance-hereditary graph (cf. [9]) is a connected graph, which preserves the distance function for induced subgraphs. That is, the distance between any two nonadjacent vertices of any connected induced subgraph of such a graph is the same as the distance between these two vertices in the original graph.Proposition 15 (see [9]).
LetG be a distance-hereditary graph, and let u be a vertex of G. Then, for each positive integer k≤maxd(u,v):v∈V and vertices v, w of the same connected component of Nk(u), one has N(v)∪Nk-1(u)=N(w)∪Nk-1(u), where the ith neighborhood of the vertex u, Ni(u)={v:d(u,v)=i}.A graphG is an interval graph if and only if there is a one-to-one correspondence between its vertices and a set of intervals on the real line, such that two vertices are adjacent if and only if the corresponding intervals have an intersection. It is also well known that a graph G is an interval graph if and only if G is chordal and asteroidal triple-free, where asteroidal triple is a set of three distinct vertices (v1,v2,v3) such that there exists a path connecting vi and vj that contains no neighbor of vk(i≠k≠j), for every combination of 1≤i,j,k≤3 (cf. [10]).A graph is a split graph if and only if its vertices can be partitioned into an independent set, and vertices which induces a clique. For simplicity, given a split graphG, we call a vertex partition of V(G)=(VI,VC), such that VI is an independent set and vertices in VC induce a clique, as an I-C-decomposition of G. It is known that a chordal graph whose complement is also a chordal graph is equivalent to a split graph (cf. [10]).A graphG is strongly chordal if and only if G is chordal, and every even cycle of length six or more contains a chord splitting the cycle into two odd length paths (cf. [10]).Ptolemaic graphs are exactly those graphs that are both chordal and distance-hereditary (cf. [11]).A graph is outerplanar if it can be drawn in the plane with all nodes in the exterior boundary. It is called maximal outerplanar if no edge can be added without destroying its outerplanar property. Every maximal outerplanar graphs is chordal (cf. [12]).Proposition 16 (see [12]).
IfG is a maximal outerplanar graph, then its central subgraph 〈Z(G)〉 is isomorphic to one of the seven graphs in Figure 1.Figure 1


## 2. Main Results

The following theorem gives a complete characterization for the odpu-self-complementary graphs. Further, given any positive even integern≠2, there exists an odpu, self-complementary graphs with odpu-number n. Also, we prove that it is possible to embed any graph G into a self-complementary, odpu-graph H with G and G¯ being induced subgraphs of the graph H. Recall that a universal vertex means a vertex which is adjacent to all other vertices of the graph.Theorem 17.
A self-complementary graphG is an odpu graph if and only if G has no universal vertex in 〈Z(G)〉.Proof.
Assume thatG is a self-complementary, odpu-graph. If v is a universal vertex in 〈Z(G)〉, then fMo(v)={1}, where M=Z(G). Hence, all the vertices of G must be adjacent to v in G. Hence, v is an isolated vertex in G¯, a contradiction to the hypothesis that G is a self-complementary graph.
Conversely, let the self-complementary graphG be without universal vertex in 〈Z(G)〉. By Proposition 7, the possible radius r and diameter d of G are r=d=2 or r=2 and d=3. If r=d=2, then the graph G is self-centered, and hence it is an odpu-graph.
Ifr=2 and d=3, then by Proposition 7, G has a dominating edge uv. In this case, the end points of the dominating edge lie in the centre, and any vertex outside the centre is adjacent to exactly one end vertex of any dominating edge.
Letx be any arbitrary vertex in Z(G). By hypothesis, x is not a universal vertex, and hence, there exists a vertex y∈Z(G) such that d(x,y)=2. Therefore, 2∈fMo(x). Also since x is adjacent to a dominating edge, 1∈fMo(x). Hence, fMo(x)={1,2} for all x∈Z(G).
Now, letv be an arbitrary vertex in G-Z(G). Then, v is adjacent to exactly one vertex of a dominating edge xy. Hence, either d(x,v)=1 and d(y,v)=2 or d(x,v)=2 and d(y,v)=1. In both cases, fMo(v)={1,2} for all v∈V(G)-Z(G), and hence G is an odpu-graph.By Theorem17 and Proposition 7, the following Corollary holds immediately.Corollary 18.
A self-complementary graphG is an odpu-graph if and only if r(G)=r(〈Z(G)〉)=2.Theorem 19.
Given any even integerk≥4, there exists a self-complementary, odpu-graph with odpu-number k.Proof.
First, we take a pathP4 and replace the end vertices of the path P4 by copies of nP2 and the interior vertices by copies of the complete n-partite graph K2,2,…,2;n≥2. Where two vertices of P4 were joined by an edge, the corresponding graphs are now joined by all possible edges between them. Let the resulting graph be G1. Clearly, G1 is a self-complementary graph of 8n vertices with diameter 3. Moreover, if we add a K2¯ and join it to all the vertices of the copies of K2,2,…,2, we get a self-complementary graph G2 of order 8n+2 and diameter 3 (see Figure 2).
Now, we claim that the odpu-number ofG1 is 4n and that of G2 is 4n+2. Since the eccentricities of the vertices in K2,2,…,2 are 2 and the eccentricities of the vertices of nP2 are 3 in G1, the center Z(G1) is the collection of all vertices of both K2,2,…,2. Since 〈Z(G1)〉 does not have a universal vertex, by Theorem 17, G1 is an odpu-graph. Let M be a minimal odpu-set of G1. For any vertex u∈Z(G1), there is exactly one vertex v∈Z(G1) such that d(u,v)=2. Hence, all the vertices of Z(G1) must be in M. Hence, od(G1)=4n.
Now, considerG2. By the same argument above, all the vertices of Z(G2) must be in the minimal odpu-set M. Hence, the odpu-number of G2 is 4n+2, hence, the theorem.Figure 2Theorem 20.
Any graphG with r(G)≥2 can be embedded into a self-complementary, odpu-graph H with both G and G¯ as induced subgraphs of H.Proof.
We construct the graphH as follows. First, consider a path P4, and replace the end vertices of the path P4 by copies of G¯ and the interior vertices by copies of G. Whenever two vertices of P4 were joined by an edge, the corresponding graphs are joined by all possible edges between them so that we get a complete bipartite graph between the vertices of the corresponding graphs. Then, the resulting graph H is self-complementary with G (and G¯) as induced subgraph of H with r(H)=2 and d(H)=3. Also, all the vertices of G belong to the centre Z(H), and the vertices of G¯ belong to H-Z(H). Let M=Z(H).
Letu∈Z(H). Since r(G)≥2, there exists a vertex v not adjacent to u in the same copy of G. But there exists a path (uwv) in H, where w is in G, for which u,v do not belong. Hence, dH(u,v)=2, and therefore, 2∈fMo(u). Since xy∈E(H) for X∈V(G1) and y∈V(G2), 1∈fMo(u). Hence, fMo(u)={1,2} for all u∈Z(H).
Letu∈V(G)-Z(G). Then, u is adjacent to a vertex w∈Z(H). Therefore, 1∈fMo(u). Also by construction, there exists a vertex v∈M such that d(u,v)=2. Hence, 2∈fMo(u). Hence, fMo(u)={1,2} for all u∈V(H)-Z(H). Hence, fMo(x)={1,2} for all x∈V(H). Hence, H is an odpu-graph.Remark 21.
Suppose that the given graph is of radius1. Then, the construction given in Theorem 20 gives that 〈Z(H)〉 has a universal vertex. Hence, by Theorem 17, the resulting graph is not an odpu-graph. So, if the given graph is of radius 1, then first embed the graph into a graph G of radius greater than or equal two, by adding a path in any one of the vertex or by any other methods in such a way that the given graph is an induced subgraph of G. Then, the graph G is of radius greater than or equal to 2, and hence, we can apply the above construction given in Theorem 20. Hence, we have the generalized form of Theorem 20, as follows.Theorem 22.
Any graphG can be embedded into a self-complementary, odpu-graph H with G and G¯ being induced subgraphs of H.The following result gives the characterization for odpu-cographs and proves that the odpu-number of an odpu-cograph is always even.Theorem 23.
A cograph (P4-free graph) G is an odpu-graph if and only if |Z(G)|≥2.Proof.
LetG be a P4-free odpu-graph. Then, clearly |Z(G)|≥2.
Conversely, letG be a cograph with |Z(G)|≥2. Since the diameter of a cograph is less than or equal to 2, the following are the only three possibilities. If (i) r(G)=d(G)=1 or (ii) r(G)=d(G)=2, then G is self-centered, and hence, it is an odpu-graph. If (iii) r(G)=1 and d(G)=2, then by assumption |Z(G)|≥2, there exist at least two universal vertices u and v in G. Therefore, {u,v}  forms an odpu-set of G, hence the theorem.Corollary 24.
A cographG is an odpu-graph if and only if r(G)=r(〈Z(G)〉).Theorem 25.
The odpu-number of an odpu-cograph is always even.Proof.
By Theorem8, each cograph is uniquely represented as a cotree and conversely. Hence, we prove the theorem using cotree characterization of cographs. Consider the cotree T of the odpu-cograph G. Since the odpu-graphs are connected, the root which is labeled by (1) in the cotree has at least two children.
If the root (1) has a child which is a leaf in the cotree, then this leaf vertexu is adjacent to all vertices of the cograph G. Hence, u is a universal vertex in G, and hence, r(G)=1. Since G is an odpu-cograph, |Z(G)|≥2, and hence, there exist two universal vertices in G. Hence, there exist at least two leaves attached to the root (1) of the cotree T. Hence, in this case od(G)=2.
So assume thatG does not have a universal vertex. Thus, there is no leaf attached to the root (1), and hence, r(G)=2. Since G is connected and all children of the root (1) are labeled by (0), the root (1) has at least two children which are labeled by (0). Let the root (1) have k children, namely, R1,R2,…,Rk, which are labeled by (0). Let M be the minimal odpu-set of G. Since r(G)=2, fMo(u)={1,2} for all u∈V(G). Also, for a cotree, each node Ri labeled by (0) at least has two leaves x and y descending from that node which are nonadjacent. Also, each leaf u descending from the node Ri is adjacent to all the leaves descending from Rj, j≠i, hence, leaves x and y with d(x,y)=2 only when x and y are descending from same Ri. So, there exist at least two vertices x and y descending from each Ri(1≤i≤k) and belonging to the minimal odpu-set M. Hence, |M|≥2k.Now, we prove thatM has exactly 2k elements. Let M be the set of 2k leaves such that the exactly two leaves x and y are descending from the same node Ri, (1≤i≤k) with xy∉E(G). Let x∈V(G). Then, there exists a y∈M which is descending from the same node Ri, where the leaf x belongs, such that xy∉E(G). Hence, d(x,y)=2, and hence, 2∈fMo(x). Since x is adjacent to all vertices in M which are descending from the nodes Rj, for all j≠i, 1∈fMo(x). Hence, fMo(x)={1,2} for all x∈V(G). Hence, od(G)=2k.Remark 26.
Given any positive even integer2n, the complete n-partite graphs K2,2,…,2 are odpu-cographs with odpu-number 2n.Next, we establish the characterization for odpu-chordal graphs.Theorem 27.
A chordal graphG is an odpu-graph if and only if r(G)=r(〈Z(G)〉).Proof.
LetG be a chordal graph with r(G) = r(〈Z(G)〉). Since r(〈Z(G)〉)≤2, there are two possibilities:(i)
r(G)=r(〈Z(G)〉)=1. Then, there are two universal vertices in G, and hence by Proposition 1, G is an odpu-graph,(ii)
r(G)=r(〈Z(G)〉)=2. By Proposition 10, dG(u,v)=d〈Z(G)〉(u,v) for allu,v∈Z(G). Let u∈Z(G). Since r(〈Z(G)〉)=2, there exists a vertex v∈Z(G) such that d(u,v)=2. Hence, 2∈fMo(u) for all u∈Z(G). Now, the connectedness of 〈Z(G)〉 ensures the existence of a vertex w∈Z(G) such that d(u,w)=1. Therefore, fMo(u)={1,2} for all u∈Z(G). Now, let u∈V(G)-Z(G).Claim 1 (2∈fMo(u)).
If there is no vertexv∈Z(G) such that d(u,v)=2, then u is adjacent to all the vertices of Z(G). Since r(〈Z(G)〉)=2, there exist two vertices x and y in Z(G) such that d(x,y)=2. Now, consider S0(x,y). Since u∉Z(G), u∉S0(x,y). But G-S0(x,y) contains an x-y (xuy)-path, which is a contradiction to the fact that G is chordal, and hence, S0⊆Z(G). Hence, there exists a vertex v∈Z(G) such that d(u,v)=2 implies 2∈fMo(u).Claim 2 (1∈fMo(u)).
Letu be nonadjacent to any of the vertices of Z(G). Let x,y∈Z(G) such that d(x,y)=2. Since r(G)=r(〈Z(G)〉)=2, d(x,u)=d(y,u)=2. Thus, there exist vertices w and z in V(G)-Z(G) such that (xwu) and (yzu) are paths of length 2 in G. If w=z, then the path (xwy)∈V(G)-S0(x,y) leads to the contradiction. Otherwise the path (xwuzy)∈V(G)-S0(x,y), a contradiction that S0(x,y)⊆Z(G). Hence, there exists a vertex v∈Z(G) such that d(u,v)=1, and hence, 1∈fMo(u) for all u∈V(G)-Z(G). Therefore, fMo(u)={1,2} for all u∈V(G)-Z(G). Hence, G is an odpu-graph.
Conversely, assume thatG is a chordal-odpu-graph. Since r(G)≤2 and 〈Z(G)〉 are connected, r(〈Z(G)〉)≤2.
Ifr(〈Z(G)〉)=1, then fMo(u)={1} for all u∈V(G). Thus, there exist at least two universal vertices in G. Hence, r(G)=1.
Ifr(〈Z(G)〉)=2, fMo(u)={1,2} for all u∈V(G). Since Z(G) is an odpu-set, the distance from any vertex of G to any vertex of Z(G) is less than or equal to 2. Thus, r(G)=2, and hence, r(G)=r(〈Z(G)〉).Corollary 28.
A chordal graphG is an odpu-graph, and then 〈Z(G)〉 is self-centered.Proof.
LetG be chordal, odpu-graphs. If 〈Z(G)〉 is not self-centered, then r(〈Z(G)〉)≠d(〈Z(G)〉). Hence, there exist vertices u,v∈Z(G) such that e〈Z(G)〉(u)≠e〈Z(G)〉(v). Let e〈Z(G)〉(u)=d(〈Z(G)〉), e〈Z(G)〉(v)=r(〈Z(G)〉), and M=Z(G). Since d〈Z(G)〉(u,v)=dG(u,v) for all u,v∈Z(G), fMo(u) has an element d(〈Z(G)〉), a contradiction.Remark 29.
The converse of Corollary28 need not be true. For example, P4 is chordal with 〈Z(P4)〉=P2, which is self-centered, but P4 is not an odpu-graph.Since interval graphs, split graphs, block graphs, ptolemaic graphs, strongly chordal graphs, and maximal outerplanar graphs are subclasses of chordal graphs, (cf. [10]), the following corollary is immediate from Theorem 27 and Corollary 28.Corollary 30.
The following classes of graphsG: interval graphs, split graphs, block graphs, ptolemaic graphs, strongly chordal graphs, or maximal outerplanar graphs are odpu-graphs if and only if r(G)=r(〈Z(G)〉), and hence, 〈Z(G)〉 is self-centered.The following theorem establishes the characterization of odpu-distance-hereditary graphs. Further, we show that the central subgraph〈Z(G)〉 of distance-hereditary-odpu-graph G is either self-centered or disconnected.Theorem 31.
LetG be a distance-hereditary graph with connected 〈Z(G)〉. Then, G is an odpu-graph if and only if r(G)=r(〈Z(G)〉).Proof.
LetG be a distance-hereditary graph with 〈Z(G)〉  which is connected. Let G be an odpu-graph. If r(G)≠r(〈Z(G)〉), then r(〈Z(G)〉)<r(G). Since 〈Z(G)〉 is connected, d〈Z(G)〉(u,v)=dG(u,v) for all u,v∈Z(G). But since r(〈Z(G)〉)<r(G), r(G)∉fMo(x) for all x∈Z(G), which is not possible. Hence, r(G)=r(〈Z(G)〉).
Conversely, letr(G)=r(〈Z(G)〉)=r. Let u∈Z(G). Then, there exists a vertex v∈Z(G) such that d(u,v)=r. Since 〈Z(G)〉 is connected, fMo(u)={1,2,…,r}.
Now, letu∈V(G)-Z(G). If 1∉fMo(u), then N1(u)∩Z(G)=ϕ, where Nt(u)={v∈V(G):d(u,v)=t}. Let k be the largest integer such that Nk(u)∩Z(G)≠ϕ, and let w∈Nk(u)∩Z(G). Then, since dG(u,w)=k, eG(w)≥k. But since u,N1(u)∉Z(G), by Proposition 15, eZ(G)(w)≤k-2. Thus, r(G)≠r(〈Z(G)〉), a contradiction. Therefore 1∈fMo(u) for all u∈V(G)-Z(G).
Now, ifr∉fMo(u), then Nr(u)∩Z(G)=ϕ. Since u∉Z(G), by Proposition 15, e〈Z(G)〉(w)≤r-1 for every w∈Z(G). Thus, r(〈Z(G)〉)<r(G), a contradiction. Hence, r∈fMo(u).
Since1,r∈fMo(u), fMo(u)={1,2,…,r} for all v∈V(G)-Z(G), hence the theorem.Corollary 32.
For a distance-hereditary-odpu-graphG, either 〈Z(G)〉 is disconnected or it is self-centered.Proof.
LetG be a distance-hereditary-odpu-graph. If 〈Z(G)〉 is connected, then we prove that 〈Z(G)〉 is self-centered. If not, let r(〈Z(G)〉)≠d(〈Z(G)〉). Let u,v∈Z(G) such that e〈Z(G)〉(u)=r(〈Z(G)〉) and e〈Z(G)〉(v)=d(〈Z(G)〉). Since G is distance-hereditary, d(〈Z(G)〉)(x,y)=dG(x,y) for all  x,y∈Z(G). Thus, d(〈Z(G)〉)∈fMo(v) and d(〈Z(G)〉)∈fMo(u), which is a contradiction, hence the theorem.Remark 33.
The converse of Corollary32 need not be true. For example, P4 is distance-hereditary and 〈Z(P4)〉=P2, which is self-centered, but P4 is not an odpu-graph.The following theorem gives a necessary condition for a maximal outerplanar graph to be an odpu-graph in terms of a specific structure of the central subgraph〈Z(G)〉.Theorem 34.
IfG is a maximal outerplanar-odpu-graph, then its central subgraph 〈Z(G)〉 is isomorphic to one of the graphs in Figure 3.Figure 3Proof.
By Proposition16, the central subgraph 〈Z(G)〉 of a maximal outerplanar graph G is isomorphic to one of the seven graphs given in Figure 1.
Since every maximal outerplanar graph is chordal, by Corollary28, the central subgraph 〈Z(G)〉 is self-centered. Therefore, 〈Z(G)〉 is isomorphic to one of the three graphs given in Figure 3, hence the theorem.Theorem 35.
A maximal outerplanar graphG is an odpu-graph if and only if it is isomorphic to one of the graphs in Figure 4.Figure 4Proof.
LetG be a maximal outerplanar-odpu-graph. By Theorem 34, 〈Z(G)〉 is isomorphic to one of the graphs in Figure 3, and by Corollary 30, r(G)=r(〈Z(G)〉). Thus, there are two cases: r(G)=r(〈Z(G)〉)=1 and r(G)=r(〈Z(G)〉)=2.Case 1 (r(G)=r(〈Z(G)〉)=1).
By Proposition1, there exist at least two universal vertices in G, and hence, 〈Z(G)〉 is isomorphic to either G1 or G2 in Figure 3. Consider all graphs G with two universal vertices. Then, P2 is the least of them. Let P2≅H1 be an edge uv. Now, add vertices one by one to get a new maximal outerplanar graph G in such a way that u and v are universal in G. That is, G=uv+{v1,v2,…,vk}, where “+” denotes the operator join (The join of two graphs G1=(V1,E1) and G2=(V2,E2) denoted by G1+G2 has the vertex set as V=V1∪V2, and the edge set E contains all the edges of G1 and G2 together with all edges joining the vertices of V1 with the vertices of V2.) of two graphs. When i=1, G=uv+v1≅C3=H2, which is a maximal outerplanar-odpu-graph. When i=2, G=uv+{v1,v2}≅K2+K2¯=H3, which is also a maximal outerplanar-odpu-graph. When i≥3, G=uv+{v1,v2,…,i}≅K2+Ki¯, i≥3 are not maximal outerplanar graphs. Thus, H1, H2, and H3 are the only maximal outerplanar graphs with r(G)=r(〈Z(G)〉)=1.Case 2 (r(G)=r(〈Z(G)〉)=2).
By Theorem34, the central subgraph is isomorphic to G3≅H4 only. Since H4 is self-centered, it is an odpu-graph. Suppose that there exists a maximal outerplanar-odpu-graph H other than H4 with 〈Z(H)〉≅G3. Then, there exists a vertex x∉V(H)-Z(H) such that x is adjacent to a vertex of 〈Z(H)〉≅G3; say the vertex a. Since H is maximal outerplanar, x cannot be adjacent to any of the vertices b, c, and a′. If there exists a vertex w such that (xwa′) is a path in the graph H, then S0(a,a′,H)⊈Z(H)=G3, a contradiction. Hence, d(x,a′)=3. Thus, eH(a′)≥3, and hence, a′∉Z(H), a contradiction. Hence, there does not exist a vertex x other than the vertices of G3. Hence, there is no maximal outerplanar-odpu-graph H other than H4 with r(G)=r(〈Z(G)〉)=2.Theorem 36.
For a maximal outerplanar graphG, the odpu-number is either 2 or 5.Proof.
By Theorem25, the maximal outerplanar odpu-graphs are one of the graphs in Figure 4.
It is enough to prove that each ofH1, H2, and H3 has odpu-number 2. Next, the graph H4 is self-centered with radius 2 and hence, fMo(u)={1,2}, for all u∈V(H4). Let M be a minimal odpu-set of H4. Hence, a′∈V(H4) is the only vertex at a distance of two from the vertex a, and hence, a′ must be in M. Similarly b′ and c′ are the only vertices of H4 at a distance of two from b and c, respectively, and hence, b′,c′∈M. Hence, |M|≥3. If M={a′,b′,c′}, then 1∉fM(u), for u=a′,b′,c′. Thus, without loss of generality, let a∈M. Then, M={a,a′,b′,c′}. But 1∉fM(a′), and hence, at least one of the vertices b and c must be in M. So let b∈M. Then, M={a,b,a′,b′,c′}. Hence, fMo(u)={1,2}, for all u∈V(H4). Thus, od(H)=5. Hence, the odpu-number of maximal outerplanar graph is either 2 or 5.Theorem 37.
For every integern≥2, there is an odpu-graph G of order n(n+2) such that its central subgraph 〈Z(G)〉 is disconnected.Proof.
Consider two disjoint complete graphsG1=Kn and G2=Kn of order n. Now, add all edges between these two complete graphs, and subdivide each of the new edges of the bipartite subgraph between G1 and G2 by one (a degree 2 vertex) to get a graph G of order n(n+2). Let the vertices of G1{v1,v2,…,vn}, the vertices of G2{u1,u2,…,un}, and wi,j the vertex which subdivides the earlier edge viuj of the bipartite graph. Then, all vertices wi,j’s have eccentricity 3 in G, and the new graph has radius 2 and diameter 3. Also the central subgraph 〈Z(G)〉 is the disjoint union of the complete graphs G1 and G2. Hence, 〈Z(G)〉 is disconnected.
Now, we prove thatG is an odpu-graph. Let M=Z(G)=V(G1)∪V(G2). For each vi∈V(G1), there exists a vj∈V(G1) such that d(vi,vj)=1, and hence, 1∈fMo(vi). Now, d(vi,uj)=2, for all  uj∈V(G2), and hence, 2∈fMo(vi). Hence, fMo(vi)={1,2} for all vi∈V(G1). Similarly, fMo(uj)={1,2} for all uj∈V(G2). Now, each vertex wi,j is adjacent to exactly vi and uj, and hence, d(wi,j,vi)=1 and d(wi,j,uj)=1. Hence, 1∈fMo(wi,j) for all i,j. Since d(wi,j,vk)=2, for all i≠k and d(wi,j,uk)=2, for all j≠k, 2∈fMo(wi,j) for all i,j. Hence, fMo(wi,j)={1,2} for all i,j, and hence, G is an odpu-graph.


## 3. Conclusion

The characterization of odpu-graphs leads to an interesting conditionr(G)=r(〈Z(G)〉), for many important classes of graphs such as chordal graphs, interval graphs, split graphs, strongly chordal graphs, self-complementary graphs, P4-free graphs, maximal outerplanar graphs, ptolemaic graphs, and distance-hereditary graphs. However, this characterization is not in general a characterization for all odpu-graphs. For example, by Theorem 37, there are classes of odpu-graphs with radius 2 and disconnected centre. That is, r(〈Z(G)〉)=∞. Thus, there are more classes of odpu-graphs which do not come under this characterization. We leave it for further scope of investigations.



---

*Source: 863439-2013-07-24.xml*