pith. sign in

Induced Saturation of $P_{6}$

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

A graph $G$ is called $H$-induced-saturated if $G$ does not contain an induced copy of $H$, but removing any edge from $G$ creates an induced copy of $H$ and adding any edge of $G^{c}$ to $G$ creates an induced copy of $H$. Martin and Smith showed that there does not exist a $P_{4}$-induced-saturated graph, where $P_{4}$ is the path on 4 vertices. Axenovich and Csik\'os studied related questions, and asked if there exists a $P_{n}$-induced-saturated graph for any $n\geq5$. Our aim in this short note is to show that there exists a $P_{6}$-induced-saturated graph.

fields

math.CO 1

years

2019 1

verdicts

UNVERDICTED 1

representative citing papers

On induced saturation for paths

math.CO · 2019-07-12 · unverdicted · novelty 8.0

Proves existence of P_{3n}-induced-saturated graphs for all positive integers n via constructions, plus Kneser graph examples for P6.

citing papers explorer

Showing 1 of 1 citing paper.

  • On induced saturation for paths math.CO · 2019-07-12 · unverdicted · none · ref 13 · internal anchor

    Proves existence of P_{3n}-induced-saturated graphs for all positive integers n via constructions, plus Kneser graph examples for P6.