-labeling of supersubdivided connected graph plus an edge

Abstract

Rosa, in his classical paper (Rosa, 1967) introduced a hierarchical series of labelings called $\rho ,\sigma ,\beta$ and $\alpha$ labeling as a tool to settle Ringel’s Conjecture which states that if $T$ is any tree with $q$ edges then the complete graph $K_{2q+1}$ can be decomposed into $2q+1$ copies of $T$. Inspired by the result of Rosa, many researchers significantly contributed to the theory of graph decomposition using graph labeling. In this direction, in 2004, Blinco, El-Zanati and Vanden Eynden introduced $\gamma$-labeling as a stronger version of $\rho$-labeling. A function $h$ defined on the vertex set of a graph $G$ with $q$ edges is called a $\gamma$-labeling if

(i) $h$ is a $\rho$-labeling of $G$,

(ii) $G$ is tripartite with vertex tripartition $(A,B,C)$ with $C=\left\{c\right\}$ and $\bar{b}\in B$ such that $(\bar{b},c)$ is the unique edge joining an element of $B$ to $c$,

(iii) for every edge $(a,v)\in E\left(G\right)$ with $a\in A$, $h\left(a\right)<h\left(v\right)$,

(iv) $h\left(c\right)-h\left(\bar{b}\right)=q$.

Further, Blinco et al. proved a significant result that if a graph $G$ with $q$ edges admits a $\gamma$-labeling, then the complete graph $K_{2cq+1}$ can be cyclically decomposed into $2cq+1$ copies of the graph $G$, where $c$ is any positive integer. Motivated by the result of Blinco et al., we show that a new family of almost bipartite graphs each admits $\gamma$-labeling. The new family of almost bipartite graphs is defined based on the supersubdivision graph of certain connected graph. Supersubdivision graph of a graph was introduced by Sethuraman and Selvaraju in Sethuraman and Selvaraju (2001). A graph is said to be a supersubdivision graph of a graph $G$ with $q$ edges, denoted $SSD\left(G\right)$ if $SSD\left(G\right)$ is obtained from $G$ by replacing every edge $e_i$ of $G$ by a complete bipartite graph $K_{2,m_i}$, $1\le i\le q$, (where $m_i$ may vary for each edge $e_i$) in such a way that the ends of $e_i$ are identified with the 2 vertices of the vertex part having two vertices of the complete bipartite graph of $K_{2,m_i}$ after removing the edge $e_i$ of $G$. In the graph $SSD\left(G\right)$, the vertices which originally belong to the graph $G$ are called the base vertices of $SSD\left(G\right)$ and all the other vertices of $SSD\left(G\right)$ are called the non-base vertices of $SSD\left(G\right)$. More precisely, we prove that if $G$ is a connected graph containing a cycle $C_k$, where $k\ge 6$ and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two, then certain supersubdivision graph of the graph $G$, $SSD\left(G\right)$ plus an edge $\hat{e}$ admits $\gamma$-labeling, where $\hat{e}$ is added between a suitably chosen pair of non-base vertices of the graph $SSD\left(G\right)$. Also, we discuss a related open problem.

Keywords:

• Gamma labeling
• Almost-bipartite graph
• Cyclic decomposition
• Supersubdivision

1 Introduction

Decomposition of a graph $H$ is a system $R$ of subgraphs of $H$ such that any edge of the graph $H$ belongs to exactly one of the subgraphs in $R$. A decomposition $R$ of a graph $H$ is said to be cyclic if $R$ contains a graph $G$ then it also contains the graph $G^{\prime }$ obtained by turning $G$. In an attempt to settle the Ringel’s Conjecture that if $T$ is any tree with $q$ edges then the complete graph $K_{2q+1}$ can be decomposed into $2q+1$ copies of $T$, Rosa in his classical paper [1] introduced a series of labelings called $\rho ,\sigma ,\beta$ and $\alpha$ labeling.

A one-to-one function $f$ from the vertex set of a graph $G$ with $q$ edges to the set $\{0,1,2,\dots ,2q\}$ is called a $\rho$-labeling of $G$ if $\{min(|f\left(u\right)-f\left(v\right)|,2q+1-|f\left(u\right)-f\left(v\right)|)|(u,v)\in E\left(G\right)\}=\{1,2,\dots ,q\}$. Let $G$ be a graph with $q$ edges. A one-to-one function $f:V\left(G\right)\to \{0,1,2,\dots ,2q\}$ is called a $\sigma$-labeling of $G$ if $\left\{|f\left(u\right)-f\left(v\right)|\right|(u,v)\in E\left(G\right)\}=\{1,2,\dots ,q\}$. $\beta$-labeling of a graph $G$ with $q$ edges is a one-to-one function $f:V\left(G\right)\to \{0,1,2,\dots ,q\}$ such that $\left\{|f\left(u\right)-f\left(v\right)|\right|(u,v)\in E\left(G\right)\}=\{1,2,\dots ,q\}$. $\beta$-labeling was later called as graceful labeling by Golomb [2] and this term is most widely used. A $\beta$-labeling $f$ of a graph $G$ with $q$ edges is called an $\alpha$-labeling if there exists an integer $k$ such that $f\left(u\right)\le k<f\left(v\right)$ or $f\left(v\right)\le k<f\left(u\right)$ for every edge $uv\in E\left(G\right)$. It is clear that $\alpha$-labeling is a stronger version of $\beta$-labeling, $\sigma$-labeling is a weaker version of $\beta$-labeling and $\sigma$-labeling is a stronger version of $\rho$-labeling.

Further, Rosa [1] proved the following two significant theorems.

Theorem 1.1

If $G$ is a graph with $q$ edges, then there exists a cyclic $G$-decomposition of $K_{2q+1}$ if and only if $G$ has a $\rho$-labeling.

Theorem 1.2

Let $G$ be a graph with $q$ edges that has an $\alpha$-labeling. Then there exists a cyclic $G$-decomposition of $K_{2cq+1}$ into subgraphs isomorphic to $G$, where $c$ is an arbitrary natural number.

The above two results inspired many researchers to discover similar labelings that can be used as a tool for decomposition of complete graphs or complete multipartite graphs. In this direction in [3] El-Zanati et al. introduced ${\rho }^{+}$-labeling. Let $G$ be bipartite graph with $q$ edges and bipartition $(A,B)$. ${\rho }^{+}$-labeling of $G$ is a one-to-one function $h:V\left(G\right)\to \{0,1,2,\dots ,2q\}$ such that the integers $h\left(x\right)-h\left(y\right)$ are distinct modulo $2q+1$ over all ordered pairs $(x,y)$ with $(x,y)\in E\left(G\right)$ and $h\left(b\right)>h\left(a\right)$ whenever $a\in A$, $b\in B$ and $(a,b)\in E\left(G\right)$. They have also proved the following decomposition theorem.

Theorem 1.3

If a bipartite graph $G$ with $q$ edges has a ${\rho }^{+}$-labeling and $x$ is any positive integer then there exists a cyclic $G$-decomposition of $K_{2qx+1}$.

In [4] Fronček introduced blended $\rho$-labeling. Let $G$ be a graph with $4k+1$ edges, $V\left(G\right)=V_0\cup V_1$, $V_0\cap V_1=\varnothing$ and $\left|V_0\right|=\left|V_1\right|=2k+1$. Let $\lambda$ be an injection, $\lambda :V_i\to \{0_i,1_i,2_i,\dots ,{\left(2k\right)}_i\}$, $i=\text{0,1}$. The pure length of an edge $(x_i,y_i)$ with $x_i,y_i\in V_i$, $i\in \{0,1\}$ is defined as $l_{ii}(x_i,y_i)=min\{|\lambda \left(x_i\right)-\lambda \left(y_i\right)|,2k+1-|\lambda \left(x_i\right)-\lambda \left(y_i\right)|\}$ for $i=\text{0,1}$ and the mixed length of an edge $(x_0,y_1)$ is defined as $l_{01}(x_0,y_1)=(\lambda \left(y_1\right)-\lambda \left(x_0\right))$ mod $2k+1$ for $x_0\in V_0,y_1\in V_1$. $G$ has a blended $\rho$-labeling if

(i)	$\left\{l_{ii}(x_i,y_i)\right|(x_i,y_i)\in E\left(G\right)\}=\{1,2,\dots ,k\}$ for $i=\text{0,1}$,
(ii)	$\left\{l_{01}(x_0,y_1)\right|(x_0,y_1)\in E\left(G\right)\}=\{1,2,\dots ,2k\}$.

Using the blended $\rho$-labeling Fronček [4] proved the following decomposition theorem.

Theorem 1.4

Let the graph $G$ with $4k+1$ edges have a blended $\rho$-labeling. Then there exists a bi-cyclic decomposition of $K_{4k+2}$ into $2k+1$ copies of $G$.

In [5] Fronček and Kubesa have examined about the decomposition of the complete graph $K_{2n}$ into $n$ isomorphic spanning trees using a new type of labeling called switching blended labeling. For more details refer [5]. In 2013, Anita Pasotti [6] introduced a generalization of graceful labeling called $d$-divisible graceful labeling as a tool to obtain cyclic $G$-decomposition in complete $m$-partite graphs with parts of size $n$, $K_{m\times n}$. Let $G$ be a graph of size $e$ and let $d$ be a divisor of $e$, say $e=d.m$. A $d$-divisible graceful labeling of $G$ is an injective function $f:V\left(G\right)\to \{0,1,2,\dots ,d(m+1)-1\}$ such that $\left\{|f\left(u\right)-f\left(v\right)|\right|(u,v)\in E\left(G\right)\}=\{1,2,\dots ,d(m+1)-1\}\setminus \{m+1,2(m+1),\dots ,(d-1)(m+1)\}$. A $d$-divisible $\alpha$-labeling of a bipartite graph $G$ is a $d$-divisible graceful labeling of $G$ having the property that its maximum value on one of the two bipartite sets does not reach its minimum value on the other one.

Further, Anita Pasotti [6] has proved the following significant theorems.

Theorem 1.5

If there exists a $d$-divisible graceful labeling of a graph $G$ of size $e$ then there exists a cyclic $G$-decomposition of $K_{(\frac{e}{d}+1)\times 2d}$.

Theorem 1.6

If there exists a $d$-divisible $\alpha$-labeling of a graph $G$ of size $e$ then there exists a cyclic $G$-decomposition of $K_{(\frac{e}{d}+1)\times 2dc}$ for any positive integer $c$.

With the motivation to decompose the complete graph $K_{2cq+1}$ into almost-bipartite graphs with $q$ edges, where $c$ is any positive integer, Blinco et al. [7] introduced $\gamma$-labeling (A graph is said to be almost-bipartite if the removal of a particular edge makes the graph bipartite). A function $h$ defined on the vertex set of a graph $G$ with $q$ edges is called a $\gamma$-labeling if

(i)	$h$ is a $\rho$-labeling of $G$,
(ii)	$G$ is tripartite with vertex tripartition $(A,B,C)$ with $C=\left\{c\right\}$ and $\bar{b}\in B$ such that $(\bar{b},c)$ is the unique edge joining an element of $B$ to $c$,
(iii)	for every edge $(a,v)\in E\left(G\right)$ with $a\in A$, $h\left(a\right)<h\left(v\right)$,
(iv)	$h\left(c\right)-h\left(\bar{b}\right)=n$.

Further, in [7], Blinco et al. have proved the following significant theorem.

Theorem 1.7

Let $G$ be a graph with $q$ edges having $\gamma$-labeling. Then there exists a cyclic $G$-decomposition of $K_{2cq+1}$, where $c$ is any positive integer.

Inspired by the above result of Blinco et al., the almost-bipartite graphs $P_n+e$, $n\ge 4$, $K_{m,n}+e$, $m\ge 2$, $n>2$, $C_{2k+1}$, $k\ge 2$, $C_{2m}+e$, $m>2$, $C_3\cup C_{4m}$, $m>1$, $C_{2k+1}\cup C_{4n+2}$, $k\ge 1$, $n\ge 1$ are found to have $\gamma$-labeling (refer [8–10,7,11]). For survey on $\gamma$-labeling refer the survey on graph labeling by Gallian [12]. In [13], Sethuraman and Selvaraju introduced a graph operation called supersubdivision of a graph that generate families of bipartite graphs from the given graph. Let $G$ be a graph with $q$ edges. A graph is said to be a supersubdivision graph of a graph $G$ with $q$ edges, denoted $SSD\left(G\right)$ if $SSD\left(G\right)$ is obtained from $G$ by replacing every edge $e_i$ of $G$ by a complete bipartite graph $K_{2,m_i}$, $1\le i\le q$, (where $m_i$ may vary for every edge $e_i$) in such a way that the ends of $e_i$ are identified with the 2-vertex part of $K_{2,m_i}$ after removing the edge $e_i$ from $G$. (In the complete bipartite graph $K_{2,m}$ the part consisting of two vertices is referred as 2-vertex part of $K_{2,m}$ and the part consisting of $m$ vertices is referred as $m$-vertex part of $K_{2,m}$). Note that for $1\le i\le q$, if $m_i=1$ for any particular edge in the supersubdivision then this results in the classic definition of subdividing a single edge. Supersubdivision graph of the graph in Fig. 1 (a) is shown in Fig. 1 (b).

Fig. 1 (a) The graph $G$ (b) Supersubdivision graph of the graph $G$.

In [14] we have proved that a family of almost bipartite graphs obtained from the supersubdivision of any tree with at least three vertices admits $\gamma$-labeling and we posed an open problem that whether supersubdivision of any connected graph plus an edge admits $\gamma$-labeling. We partially answer this question by proving the following result. Let $G$ be a connected graph containing a cycle $C_k$, where $k\ge 6$ and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two. Then certain supersubdivision graph of the graph $G$, $SSD\left(G\right)$ plus an edge $\hat{e}$ admits $\gamma$-labeling, where $\hat{e}$ is added between a suitably chosen pair of non-base vertices of the graph $SSD\left(G\right)$. Also, we discuss a related open problem.

2 Main result

In this section we first present Algorithm 1 to construct supersubdivision graph of a connected graph containing a cycle $C_k$, where $k\ge 6$ and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two. Then we prove that certain supersubdivision graph of the graph $G$, $SSD\left(G\right)$ plus an edge $\hat{e}$ admits $\gamma$-labeling, where $\hat{e}$ is added between a suitably chosen pair of non-base vertices of the graph $SSD\left(G\right)$.

Algorithm 1

Construction of Supersubdivision Graphs Input. Any connected graph $G$ containing a cycle $C_k$, where $k\ge 6$ and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two.

Step 1. Naming the vertices of $G$ by BFS algorithm.

Find a vertex of degree two having one adjacent vertex with degree one and the other adjacent vertex with degree at least two. Refer such a vertex of degree two by $v$, its unique adjacent vertex of degree one by $w$ and the unique adjacent vertex of degree at least two by $u$. Obtain the graph $G\setminus \{v,w\}$, denote the graph thus obtained as $\tilde{G}$. Considering the vertex $u$ as the root of $\tilde{G}$, run BFS on $\tilde{G}$ and obtain the BFS ordering of the vertices in $\tilde{G}$ as $v_0,v_1,\dots ,v_{n-1}$, where $v_0$ is the root $u$ and $n=\left|V\left(\tilde{G}\right)\right|$. Then name the vertex $v$ as $v_{n+1}$ and $w$ as $v_n$ in the graph $G$. [Thus, the vertices of $G$ are ordered (or named) as $v_0,v_1,\dots ,v_{n-1},v_n,v_{n+1}$].

Step 3. Edge ordering

Denote the edges $v_0{v}_{n+1},v_{n+1}{v}_n$ as $e_1,e_2$ respectively. Among all the adjacent vertices of $v_{n-1}$, find the vertex with label having the largest index, say $v_{k_1}$. Then denote the edge $v_{n-1}{v}_{k_1}$ by $e_3$. Then find the adjacent vertex of $v_{n-1}$ with the label having the largest possible index less than $k_1$, say $v_{k_2}$. Then denote the edge $v_{n-1}{v}_{k_2}$ by $e_4$. Similarly, sequentially find the adjacent vertices $v_{k_3},v_{k_4},\dots ,v_{k_{d^{\prime }}}$ of $v_{n-1}$ and label the edges $v_{n-1}{v}_{k_3},v_{n-1}{v}_{k_4},\dots ,v_{n-1}{v}_{k_{d^{\prime }}}$ by $e_5,e_6,\dots ,e_{d^{\prime }+2}$, where $d^{\prime }$ is the degree of $v_{n-1}$ and $k_1>k_2>k_3>\cdots k_{d^{\prime }}$. For $j$, $2\le j\le n-1$ in the increasing order of $j$, find the adjacent vertices of $v_{n-j}$, then label the incident edges at $v_{n-j}$ in the increasing order of $j$ sequentially as done above as $e_{d^{\prime }+3},e_{d^{\prime }+4},\dots ,e_q$, where $q$ denotes the number of edges of the graph $G$.

Step 4. Defining basic labels

Define $f\left(v_i\right)=i$, for $i$, $0\le i\le n+1$.

Step 5. Edge replacement

Step 5.1. Replacement of the edge $e_q=v_0{v}_1$

Replace the edge $e_q=v_0{v}_1$ by $K_{2,m_q}$, where $m_q\ge 2$ is any positive integer in such a way that the ends $v_0$ and $v_1$ of $e_q$ are identified with the 2-vertex part of $K_{2,m_q}$.

Step 5.2. Replacement of the edge $e_1=v_0{v}_{n+1}$

Replace the edge $e_1=v_0{v}_{n+1}$ by $K_{2,m_1}$ in such a way that the ends $v_0$ and $v_{n+1}$ of $e_1$ are identified with the 2-vertex part of $K_{2,m_1}$, where $m_1$ is defined depending on the congruence class of $n+2$ modulo 4 as given in Table 1.

Table 1 Value of $m_1$ depending on the congruence class of $n+2$ modulo 4.

Congruence class of $n+2$ mod 4	$m_1$
$4k$, $k\ge 2$	$2k-1$
$4k+1$, $k\ge 2$	$2k$
$4k+2$, $k\ge 2$	$2k+1$
$4k+3$, $k\ge 2$	$2k+2$

Step 5.3. Replacement of the edge $e_2=v_{n+1}{v}_n$.

Replace the edge $e_2=v_{n+1}{v}_n$ by $K_{2,m_2}$ in such a way that the ends $v_{n+1}$ and $v_n$ of $e_2$ are identified with the 2-vertex part of $K_{2,m_2}$, where $m_2$ is defined depending on the nature of $n$ as given in Table 2.

Table 2 Value of $m_2$ depending on the nature of $n$.

Nature of $n$	$m_2$
$6\le n\le 9$	2
$n\ge 10$	$\lfloor \frac{n+2}{4}\rfloor$

Step 5.4. Replacement of the edge $e_i=v_x{v}_y$ for $i$, $3\le i\le q-1$.

Replace every edge $e_i=v_x{v}_y$ for $i$, $3\le i\le q-1$ by $K_{2,m_i}$, where $m_i=t_i|f\left(v_x\right)-f\left(v_y\right)|=t_i|x-y|$, $0\le x,y\le n-1$, $t_i$ is an arbitrary positive integer in such a way that the end vertices of $e_i$ are identified with the 2-vertex part of $K_{2,m_i}$.

Notation 1

For a given connected graph $G$, the supersubdivision graph of $G$ constructed by Algorithm 1 is denoted by $SSD\left(G\right)$.

Notation 2

The vertex set of the graph $SSD\left(G\right)$, $V\left(SSD\left(G\right)\right)$ can be partitioned into two sets $B\left(SSD\left(G\right)\right)$ and $NB\left(SSD\left(G\right)\right)$, where $B\left(SSD\left(G\right)\right)$ is the set of all actual vertices of $G$ in $SSD\left(G\right)$ called base vertices of $SSD\left(G\right)$ and $NB\left(SSD\left(G\right)\right)$ is the set of vertices which lie in the $m_i$-part of the complete bipartite graph $K_{2,m_i}$ which replaces the edge $e_i$ of $G$ in construction of the graph $SSD\left(G\right)$, for $1\le i\le q$ and they are called non-base vertices of $SSD\left(G\right)$.

Theorem 2.1

Let $G$ be a connected graph containing a cycle $C_k$, where $k\ge 6$ and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two. Then certain supersubdivision graph of the graph $G$, $SSD\left(G\right)$ plus an edge $\hat{e}$ admits $\gamma$-labeling, where $\hat{e}$ is added between a suitably chosen pair of non-base vertices of the graph $SSD\left(G\right)$.

Proof

Let $G$ be a connected graph containing a cycle $C_k$, where $k\ge 6$ and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two. Then, the supersubdivision graph of the graph $G$, $SSD\left(G\right)$ is obtained by using Algorithm 1. Consider the graph $SSD\left(G\right)+\hat{e}$, where $\hat{e}$ is the new edge joining any two of the non-base vertices say $u$ and $v$ of the $m_q$-vertex part of the complete bipartite graph $K_{2,m_q}$ which replaces the edge $e_q$ of the graph $SSD\left(G\right)$. From the construction, we observe that, the graph $SSD\left(G\right)+\hat{e}$ has $n+2+{\sum }_{i=1}^q{m}_i$ vertices and $M=2{\sum }_{i=1}^q{m}_i+1$ edges, where $n+2$ is the number of vertices of the graph $G$, $q$ is the number of edges of the graph $G$ and $m_i$ is the number of vertices in the $m_i$-part of $K_{2,m_i}$ which replaces the edge $e_i$ in constructing $SSD\left(G\right)$, for $1\le i\le q$. That is, $\left|V(SSD\left(G\right)+\hat{e})\right|=n+2+{\sum }_{i=1}^q{m}_i$ and $\left|E(SSD\left(G\right)+\hat{e})\right|=M=2{\sum }_{i=1}^q{m}_i+1$.

By Notation 2, $V\left(SSD\left(G\right)\right)=B\left(SSD\left(G\right)\right)\cup NB\left(SSD\left(G\right)\right)$, where $B\left(SSD\left(G\right)\right)$ is the set of base vertices of $SSD\left(G\right)$ and $NB\left(SSD\left(G\right)\right)$ is the set of non-base vertices of $SSD\left(G\right)$.

Defining vertex labeling $g$ on the base vertices of $SSD\left(G\right)+\hat{e}$.

Define $g\left(v_i\right)=f\left(v_i\right)=i$, for $i$, $0\le i\le n+1$.

Defining vertex labeling $g$ on the non-base vertices of $SSD\left(G\right)+\hat{e}$.

First we define labels on the non-base vertices of the complete bipartite graphs $K_{2,m_1}$, $K_{2,m_2}$ which replace the edges $v_0{v}_{n+1}$, $v_n{v}_{n+1}$ respectively in constructing $SSD\left(G\right)$, as shown in Fig. 2.

Fig. 2 Labels of vertices and edges of $K_{2,m_1}$ and $K_{2,m_2}$.

For $1\le i\le n-2$, we find all the adjacent vertices $v_{n-i-r_{i1}},v_{n-i-r_{i2}},\dots ,v_{n-i-r_{i{p}_i}}$ of $v_{n-i}$ satisfying the index property $1\le r_{i1}<r_{i2}<\cdots <r_{i{p}_i}<n-i$. [Note that, here $p_i$ denotes the number of such adjacent vertices of $v_{n-i}$] For each $i$, $1\le i\le n-2$ and for $j$, $1\le j\le p_i$, we consider the edge $v_{n-i}{v}_{n-i-r_{ij}}$ of $G$ and the complete bipartite graph $K_{2,t_{ij}{r}_{ij}}$ which replaces the edge $v_{n-i}{v}_{n-i-r_{ij}}$in constructing $SSD\left(G\right)$, where $t_{ij}$ is any positive integer and $r_{ij}$ is obtained as $|(n-i)-(n-i-r_{ij})|$. Now, in order to define the labels for the non-base vertices of $K_{2,t_{ij}{r}_{ij}}$ we introduce the following parameters.

For the case $j=i=1$, define $N_{r_{11}}=n+m_1+2m_2+3+a$, where $a$ is defined depending on the congruence class of $n+2$ modulo 4 as given in Table 3.

Table 3 Value of $a$ depending on the congruence class of $n+2$ modulo 4.

Congruence class $n+2$ mod 4	$a$
$4k$, $k\ge 2$	$2k-2$
$4k+1$, $k\ge 2$	$2k-1$
$4k+2$, $k\ge 2$	$2k$
$4k+3$, $k\ge 2$	$2k+1$

Define $N_{r_{1j}}=N_{r_{1(j-1)}}+2t_{1(j-1)}{r}_{1(j-1)}$, for $2\le j\le p_1$.

For each $i$, $2\le i\le n-2$, define $$N_{r_{ij}}=\left\{\begin{array}{cc}{N}_{r_{(i-1)p_i}}+2t_{(i-1)p_i}{r}_{(i-1)p_i}-1,\hfill & \text{when}j=1\hfill \\ N_{r_{i(j-1)}}+2t_{i(j-1)}{r}_{i(j-1)},\hfill & \text{when}2\le j\le p_i.\hfill \end{array}\right.$$Then, for $1\le i\le n-2$ and for $j$, $1\le j\le p_i$, the labels of the non-base vertices of the complete bipartite graph $K_{2,t_{ij}{r}_{ij}}$ which replaces the edge $v_{n-i}{v}_{n-i-r_{ij}}$ of $G$ in constructing the graph $SSD\left(G\right)$ is defined as shown in Fig. 3. From the above labeling given in Figs. 2 and 3, it is clear that, except the non-base vertices of the complete bipartite graph $K_{2,m}$ which replaces the edge $v_0{v}_1$, all the other non-base vertices of the complete bipartite graph $K_{2,t_{ij}{r}_{ij}}$ which replaces the edge $v_{n-i}{v}_{n-i-r_{ij}}$ for each $i$, $1\le i\le n-2$ and for $j$, $1\le j\le p_i$ are labeled.

Fig. 3 Labels of vertices and edges of $K_{2,t_{ij}{r}_{ij}}$ for each $i$, $1\le i\le n-2$ and for $j$, $1\le i\le p_i$.

Now, we consider the complete bipartite graph $K_{2,m}$ which replaces the edge $v_0{v}_1$ in constructing $SSD\left(G\right)$ and we define labels for the non-base vertices of $K_{2,m}$ as shown in Fig. 4.

Fig. 4 Labels of vertices and edges of the complete bipartite graph which replaces the edge $v_0{v}_1$.

Observation 1

Vertex labels of $SSD\left(G\right)$ are distinct.

The labels of base vertices of $SSD\left(G\right)$ form an increasing sequence $S_1:(0,1,2,\dots ,n-1,n,n+1)$. Thus they are distinct. From Fig. 2, it is clear that the labels of the non-base vertices of the complete bipartite graphs $K_{2,m_1}$ and $K_{2,m_2}$ form an increasing sequence, $$S_2:(n+2,n+5,n+7,\dots ,n+m_1+2,n+m_1+3,n+m_1+4,n+m_1+6,n+m_1+8,\dots ,n+m_1+2m_2,n+m_1+2m_2+3).$$Note that, maximum of $S_1<$ minimum of $S_2$. Thus, $S_1\cup S_2$ is also an increasing sequence.

From the definition of $N_{r_{11}}$, it is clear that the difference between the label of the first non-base vertex of the complete bipartite graph $K_{2,t_{11}{r}_{11}}$ which replaces the edge $v_{n-1}{v}_{n-1-r_{11}}$ and the last non-base vertex of the complete bipartite graph $K_{2,m_2}$ which replaces the edge $v_n{v}_{n+1}$ is $a$, where the value of $a$ is defined in Table 3.

For $2\le j\le p_1$, from the definition of $N_{r_{1j}}$, it is clear that the difference between the label of the first non-base vertex of the complete bipartite graph $K_{2,t_{1j}{r}_{ij}}$ and the label of the last non-base vertex of the complete bipartite graph $K_{2,t_{1(j-1)}{r}_{1(j-1)}}$ is $N_{r_{1j}}-N_{r_{1(j-1)}}-(2t_{1(j-1)}-1)r_{1(j-1)}+1$.

For each $i$, $2\le i\le n-2$ and for $j$, $1\le j\le p_i$, from the definition of $N_{r_{ij}}$, it is also clear that the difference between the label of the first non-base vertex of the complete bipartite graph $K_{2,t_{ij}{r}_{ij}}$ and the last non-base vertex of the complete bipartite graph $K_{2,t_{(i-1)p_{i-1}}{r}_{(i-1)p_{i-1}}}$ is $N_{r_{ij}}-N_{r_{(i-1)p_{i-1}}}-(2t_{(i-1)p_{i-1}}-1)r_{(i-1)p_{i-1}}+1$.

From Fig. 3, we observe that the labels of the non-base vertices in the first set of $K_{2,t_{ij}{r}_{ij}}$ increase consecutively by one. Hence the labels of all the non-base vertices of the first set of $K_{2,t_{ij}{r}_{ij}}$ are distinct. Further, we observe that the least value of the labels of the first set of $K_{2,t_{ij}{r}_{ij}}$ is $N_{r_{ij}}+r_{ij}-1$ and the largest value of the labels of the non-base vertices of the second set of $K_{2,t_{ij}{r}_{ij}}$ is $N_{r_{ij}}+2r_{ij}$ and their difference is $r_{ij}+1$. As in the first set, the labels of the non-base vertices of the second set also increase by one consecutively. Hence, the labels of all the non-base vertices of the second set of $K_{2,t_{ij}{r}_{ij}}$ are also distinct. Similarly, the labels of the non-base vertices of the other remaining $t_{ij}-2$ sets of $K_{2,t_{ij}{r}_{ij}}$ are distinct.

From Fig. 4, observe that the labels of the non-base vertices of the complete bipartite graph $K_{2,m}$ form an increasing sequence, $$(N_{r_{10}},N_{r_{10}}+2,N_{r_{10}}+4,\dots ,M-1,2M-1).$$Thus, the labels of vertices of $SSD\left(G\right)$ can be arranged as a monotonically increasing sequence. Hence the vertex labels of the graph $SSD\left(G\right)$ are distinct.

Observation 2

Edge labels of $SSD\left(G\right)+\hat{e}$ are distinct.

Since the labels of the edges $v_{0}v,v_{1}v$ are $2M-1,2M-2$ respectively (which are beyond $M$), we consider their edge labels as $2M+1-|g\left(v\right)-g\left(v_0\right)|=2M+1-(2M-1)=2$ and $2M+1-|g\left(v\right)-g\left(v_1\right)|=2M+1-(2M-2)=3$ respectively. From Fig. 2, we observe that the labels of the edges of $K_{2,m_1}$ and $K_{2,m_2}$ can be arranged as the following sequences, $$1,(4,5,6,\dots ,m_1+1,m_1+2),(m_1+3,m_1+4,m_1+5,\dots ,m_1+2m_2-1,m_1+2m_2),(n+2=m_1+2m_2+1),(m_1+2m_2+2,m_1+2m_2+3),(n+5=m_1+2m_2+4,n+6=m_1+2m_2+5,\dots ,n+m_1+2=2m_1+2m_2+1,n+m_1+3=2m_1+2m_2+2).$$From Fig. 3, we observe that the $2r_{ij}$ edges of the first set of $K_{2,t_{ij}{r}_{ij}}$ get distinct values from $$N_{r_{ij}}-n+i\text{to}{N}_{r_{ij}}-n+i+2r_{ij}-1,$$the $2r_{ij}$ edges of the second set of $K_{2,t_{ij}{r}_{ij}}$ get distinct values from $$N_{r_{ij}}-n+i+2r_{ij}\text{to}{N}_{r_{ij}}-n+i+4r_{ij}-1$$and finally, the $2r_{ij}$ edges of the $t_{ij}^{th}$ set of $K_{2,t_{ij}{r}_{ij}}$ get distinct values from $$N_{r_{ij}}-n+i+2(t_{ij}-1)r_{ij}\text{to}{N}_{r_{ij}}-n+i+2t_{ij}{r}_{ij}-1.$$Thus, the $2t_{ij}{r}_{ij}$ edges of $K_{2,t_{ij}{r}_{ij}}$ can be arranged as a sequence, $$N_{r_{ij}}-n+i,N_{r_{ij}}-n+i+1,\dots ,N_{r_{ij}}-n+i+2t_{ij}{r}_{ij}-2,N_{r_{ij}}-n+i+2t_{ij}{r}_{ij}-1.$$From Fig. 4, the labels of the edges of $K_{2,m}$ can be arranged as three sequences, $$(N_{r_{10}}-1,N_{r_{10}},N_{r_{10}}+1,N_{r_{10}}+2,\dots ,M-2,M-1),M,(3,2).$$Thus, from Figs. 2–4, it is clear that the labels of edges of $SSD\left(G\right)+\hat{e}$ can be arranged as a monotonically increasing sequence from 1 to $M$.

Hence the edge labels of $SSD\left(G\right)+\hat{e}$ are distinct.

Observation 3

$g$ is a $\gamma$-labeling.

In order to prove that $g$ is a $\gamma$-labeling, we partition the vertex set $V\left(SSD\left(G\right)\right)$ as $(X,Y,Z)$, where $X=B\left(SSD\left(G\right)\right)$, $Y=NB\left(SSD\left(G\right)\right)\setminus \left\{v\right\}$ and $Z=\left\{v\right\}$. Then, by the above labeling, we have $g\left(v_k\right)<g\left(u_{ij}\right)$ for any $v_k\in X$ and for any $u_{ij}\in Y\cup Z$.

The label of the edge $uv=M=(2M-1-(M-1))$.

Hence, from Observations 1–3, the graph $SSD\left(G\right)+\hat{e}$ admits $\gamma$-labeling. □

Illustration

We illustrate below the $\gamma$-labeling that is defined as in the proof of Theorem 2.1. The connected graph $G$ with edge labels is given in Fig. 5.

Fig. 5 The connected graph $G$ with edge labels.

The $\gamma$-labeled $SSD\left(G\right)+\hat{e}$, where the $\gamma$-labeling as defined in the proof of Theorem 2.1 is given in Fig. 6. Note that $\hat{e}=(104,209)$.

Fig. 6 $\gamma$-labeling of $SSD\left(G\right)+\hat{e}$.

As the graph $SSD\left(G\right)+\hat{e}$ admits $\gamma$-labeling, from Theorems 1.7 and 2.1 we have the following corollary.

Corollary 2.2

The complete graph $K_{2cm+1}$ can be cyclically decomposed into copies of the graph $SSD\left(G\right)+\hat{e}$, where $G$ is a connected graph containing a cycle $C_k$, where $k\ge 6$ and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two, $SSD\left(G\right)+\hat{e}$ is certain supersubdivision graph of the graph $G$ plus an edge $\hat{e}$ added between suitably chosen pair of non-base vertices of the graph $SSD\left(G\right)$, $c$ is any positive integer and $m=\left|E(SSD\left(G\right)+\hat{e})\right|$.

3 Discussion

In Section 2, we consider the connected graph $G$ containing a cycle $C_k$, where $k\ge 6$ and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two. Then the graph $SSD\left(G\right)+\hat{e}$ is obtained from certain supersubdivision graph of the graph $G$ and adding an edge $\hat{e}$ between suitably chosen pair of non-base vertices in $SSD\left(G\right)$. In Theorem 2.1 for such special connected graph $G$, we have shown that $SSD\left(G\right)+\hat{e}$ admits $\gamma$-labeling. We strongly feel that supersubdivision of any connected graph $G$ with one additional edge would also admit $\gamma$-labeling and also from the inspiration of the result of Sethuraman and Selvaraju [15] we pose the following conjecture,

Supersubdivision of any connected graph $G$ plus an edge $\hat{e}$, $SSD\left(G\right)+\hat{e}$ admits $\gamma$-labeling, where $\hat{e}$ is added between suitably chosen pair of non-base vertices of $SSD\left(G\right)$.