# The existence of a specific kind of independent set in a connected graph satisfying the following property

Suppose $$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), i.e. of an induced $$K_{ 1,2}$$.

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}\}.$$ My question is whether it is possible that for any given integer $$n\geq1$$, we can always find $$G$$ such that $$D(G)>n$$.

• Not always. For G an odd cycle on more than three vertices, I believe no such independent set E exists. Gerhard "Possibly True For Bipartite Graphs" Paseman, 2018.08.25. Aug 26 '18 at 3:47
• just a nitpick - do not use $E$ to denote both edges of $G$ and an independent set. Aug 26 '18 at 8:41
• you are also not following the standard in graph theory convention that a triangle is a complete subgraph on 3 vertices. Aug 26 '18 at 8:50
• as well, I think, it is important whether $G$ is finite, or not. Aug 26 '18 at 8:52
• Possible duplicate of Asking for an example of a graph $G$ satisfying the following property
– bof
Aug 28 '18 at 11:23

For $n\in\mathbb N$ we have $D(K_2\square K_{n+2})=D((C_{3n+2})^n)=n.$

(I posted these examples in my answer to your other question before I looked at this question.)