Isolation critical graphs under multiple edge subdivision
It addresses a theoretical problem in graph theory by characterizing graphs based on isolation number changes under edge subdivision, which is incremental to existing graph theory research.
This paper introduces the concept of (ι,q)-critical graphs, which relate to the isolation number of graphs under edge subdivision, and proves that such graphs exist for all integers q≥1, with a best-possible bound of q≤m−1 for connected non-star graphs with m edges.
This paper introduces the notion of an $(ι,q)$-critical graph. The isolation number of a graph $G$, denoted by $ι(G)$ and also known as the vertex-edge domination number of $G$, is the size of a smallest subset $D$ of the vertex set of $G$ such that the subgraph induced by the set of vertices that are not in the closed neighbourhood of $D$ has no edges. A graph $G$ is $(ι,q)$-critical if every subdivision of $q$ edges of $G$ gives a graph whose isolation number is greater than $ι(G)$, and $G$ has $q-1$ edges such that subdividing them gives a graph whose isolation number is $ι(G)$. We show that an $(ι,q)$-critical graph exists for every integer $q \ge 1$. We prove that if $G$ is a connected $m$-edge non-star graph, then $G$ is $(ι,q)$-critical for some $q \le m - 1$. We show that this bound is best possible. We provide a general characterization of $(ι,1)$-critical graphs as well as a constructive characterization of $(ι,1)$-critical trees, demonstrating that $(ι,1)$-criticality can be checked in linear time for trees.