Some new classes of open distance-pattern uniform graphs (Q2248722)

Summary: Given an arbitrary nonempty subset \(M\) of vertices in a graph \(G=(V,E)\), each vertex \(u\) in \(G\) is associated with the set \(f_M^0(u)=\{d(u,v):v\in M,u\neq 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 \(f_M^0(u)=f_M^0(v)\) for all \(u,v\in 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 \(\mathrm{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 \(\overline G\) are induced subgraphs of \(H\). We also prove that the odpu-number of a maximal outerplanar graph is either 2 or 5.