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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.