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

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 26 '18 at 3:47
  • $\begingroup$ just a nitpick - do not use $E$ to denote both edges of $G$ and an independent set. $\endgroup$ Aug 26 '18 at 8:41
  • 2
    $\begingroup$ you are also not following the standard in graph theory convention that a triangle is a complete subgraph on 3 vertices. $\endgroup$ Aug 26 '18 at 8:50
  • $\begingroup$ as well, I think, it is important whether $G$ is finite, or not. $\endgroup$ Aug 26 '18 at 8:52
  • 1
    $\begingroup$ Possible duplicate of Asking for an example of a graph $G$ satisfying the following property $\endgroup$
    – 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.)


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.