Embedding in distance degree regular and distance degree injective graphs

Medha Itagi Huilgola,* M. Rajeshwarib and S. Syed Asif Ullac

Embedding in distance degree regular and distance degree injective graphs

Authors :

Medha Itagi Huilgol^a,*M. Rajeshwari^b and S. Syed Asif Ulla^c

Author Address :

^a,b,cDepartment of Mathematics, Bangalore University, Central College Campus, Bangalore - 560 001, India .

*Corresponding author.

Abstract :

The eccentricity $e(u)$ of a vertex $u$ is the maximum distance of $u$ to any other vertex of $G$.The distance degree sequence (dds) of a vertex $u$ in a graph $G=(V,E)$ is a list of the number of vertices at distance 1, 2,\ldots, $e(u)$ in that order, where $e(u)$ denotes the eccentricity of $u$ in $G$. Thus the sequence $(d_{i_{0}},d_{i_{1}},d_{i_{2}},\ldots,d_{i_{j}},\ldots)$ is the dds of the vertex $v_{i}$ in $G$ where $d_{i_{j}}$ denotes number of vertices at distance $j$ from $v_{i}$. A graph is distance degree regular (DDR) graph if all vertices have the same dds. A graph is distance degree injective (DDI) graph if no two vertices have the same dds.

In this paper, we consider the construction of a DDR graph having any given graph $G$ as its induced subgraph. Also we consider construction of some special class of DDI graphs.

Keywords :

Distance degree sequence, Distance degree regular (DDR) graphs, Almost DDR graphs, Distance degree injective(DDI) graphs.

DOI :

Article Info :

Received : March 31, 2013; Accepted : August 05, 2013.