Given an arbitrary nonempty subsetMof vertices in a graphG=(V,E), each vertexuinGis associated with the setfMo(u)={d(u,v):v∈M,u≠v}and called its openM-distance-pattern. The graphGis called open distance-pattern uniform (odpu-) graph if there exists a subsetMofV(G)such thatfMo(u)=fMo(v)for allu,v∈V(G),andMis called an open distance-pattern uniform (odpu-) set ofG.The minimum cardinality of an odpu-set inG, if it exists, is called the odpu-number ofGand is denoted byod(G). Given some propertyP, we establish characterization of odpu-graph with propertyP. 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 graphGcan be embedded into a self-complementary odpu-graphH, such thatGandG¯are induced subgraphs ofH. We also prove that the odpu-number of a maximal outerplanar graph is either2or5.
展开▼
