2
$\begingroup$

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$.

$\endgroup$
2
  • 1
    $\begingroup$ 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.$ $\endgroup$
    – bof
    Commented Aug 28, 2018 at 4:18
  • $\begingroup$ I edited my answer to include another family of examples. $\endgroup$
    – bof
    Commented Aug 28, 2018 at 11:03

1 Answer 1

2
$\begingroup$

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.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .