Some New Classes of Open Distance-Pattern Uniform Graphs

Abstract EN

Given an arbitrary nonempty subset M 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.