pith. sign in

arxiv: 1901.09801 · v1 · pith:ZAKWAXJXnew · submitted 2019-01-28 · 🧮 math.CO

Induced Saturation of P₆

classification 🧮 math.CO
keywords graphinducedinduced-saturatedcopytherecreatesedgeexists
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On induced saturation for paths

    math.CO 2019-07 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.