# Asking for an example of a graph $G$ satisfying the following property

This question comes from another question I submitted earlier.

Let $G$ be a finite graph. For any independent set $S$ in $G$ with $|S|\geqslant2$ and $v\in S$, define $$d_S(v)=\mid\{u\in V(G)\setminus S:N_G(u)\cap S=\{v\}\}\mid$$ and $$D_S=\max\{d_S(v):v\in S\},\\D(G)=\min\{D_S:\text{S ranges over all independent sets in G with |S|\geqslant2}\}.$$ We call $G$ a $T$-graph if $G$ is a connected finite graph satisfying that every edge $uv$ of $G$ belongs to a "triangle" $uvw$ such that $uv,uw\in E(G),\ vw\notin E(G)$ or $uv,vw\in E(G),\ uw\notin E(G)$(in other words, every edge of $G$ is part of a vee shape).

From a comment in this question, I know that if $G$ is an odd cycle on more than three vertices, then $G$ is a $T$-graph with $D(G)=1$. But I can not find a $T$-graph $G$ with $D(G)\geqslant2$, so I submit this question to ask for an example of such $G$.

• I think your definition of $T$-graph can be put more succinctly as $$uv\in E(G)\implies N_G[u]\ne N_G[v]$$ where $N_G[v]=N_G(v)\cup\{v\}$ is the closed neighborhood of the vertex $v.$
– bof
Aug 28 '18 at 4:18
• I edited my answer to include another family of examples.
– bof
Aug 28 '18 at 11:03

## 1 Answer

For $n\ge2$ the Cartesian product graph $G_n=K_2\square K_n$ is a $T$-graph and $D(G_n)=n-2.$

$G_n$ has vertices $u_1,u_2,\dots,u_n$ and $v_1,v_2,\dots,v_n,$ and edges $u_iv_i\ (i=1,2,\dots,n)$ and $u_iu_j,\ v_iv_j\ (i\ne j).$ If $S$ is an independent set in $G_n$ with $|S|\ge2$ and $v\in S,$ then $|S|=2$ and $d_S(v)=n-2.$

$G=G_4$ is an example of a $4$-regular $T$-graph of order $8$ with $D(G)=2.$ Another graph with these properties is $(C_8)^2,$ i.e., take the vertices of a regular octagon and join each vertex to its four nearest neighbors. More generally, $H_n=(C_{3n+2})^n$ is a $2n$-regular $T$-graph of order $3n+2$ with $D(H_n)=n.$