%0 Journal Article
%T Some New Classes of Open Distance-Pattern Uniform Graphs
%A Bibin K. Jose
%J International Journal of Combinatorics
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/863439
%X Given an arbitrary nonempty subset of vertices in a graph , each vertex in is associated with the set and called its open -distance-pattern. The graph is called open distance-pattern uniform (odpu-) graph if there exists a subset of such that for all and is called an open distance-pattern uniform (odpu-) set of The minimum cardinality of an odpu-set in , if it exists, is called the odpu-number of and is denoted by . Given some property , we establish characterization of odpu-graph with property . 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 can be embedded into a self-complementary odpu-graph , such that and are induced subgraphs of . We also prove that the odpu-number of a maximal outerplanar graph is either or . 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 of vertices in a graph , the open -distance-pattern of a vertex in is defined to be the set , where denotes the distance between the vertices and in . If there exists a nonempty set such that is independent of the choice of , then is called open distance-pattern uniform (odpu-) graph, and the set is called an open distance-pattern uniform (odpu-) set. The minimum cardinality of an odpu-set in , if it exists, is the odpu-number of and is denoted by . 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 vertex in a connected graph , the eccentricity of is the distance to a vertex farthest from . The minimum eccentricity among the vertices of a connected graph is the radius of , denoted by , and the maximum eccentricity is its diameter, . A vertex in a connected graph is called a central vertex if . The collection of all central vertices is called the center of denoted by . In paper [2], it is proved that a graph with radius is an odpu graph if and
%U http://www.hindawi.com/journals/ijcom/2013/863439/