\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{blindtext} \usepackage{array} \usepackage{amsthm, amsmath, amssymb,tikz, caption, subcaption} \usepackage{multirow}%allows a table cell to span multiple rows \usepackage{caption, subcaption}%for messing with captions \usepackage{enumitem} \usepackage{float}%can force table location, need \begin{table}[H] instead of [htdp] \restylefloat{table} %for table of contents with links: \usepackage{color} \usepackage[colorlinks=true, citecolor=black,linkcolor=black, urlcolor=blue]{hyperref} \usetikzlibrary{calc} %vertex styles \tikzstyle{vx}=[shape=circle, minimum size=2mm, inner sep=0, fill=black] \tikzstyle{whitevx}=[shape=circle, minimum size=2mm, draw=black, thick, fill=white, inner sep=0]%formerly red \tikzstyle{grayvx}=[shape=circle, minimum size=2mm, draw=black, thick, dash pattern = on 2pt off 1 pt, fill=gray!90, inner sep=0] %edge styles \tikzstyle{grayedge}=[line width=2.5pt,dash pattern=on 1pt off 1pt] \tikzstyle{sgrayedge}=[line width=1.875pt,dash pattern=on 1pt off 1pt] \tikzstyle{emphedge}=[ultra thick, dotted] %Theorems \theoremstyle{plain} \newtheorem{thm}{Theorem}[section] \newtheorem{lem}[thm]{Lemma} \newtheorem{lemma}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{claim}[thm]{Claim} \newtheorem{cor}[thm]{Corollary} \newtheorem{obs}[thm]{Observation} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \newtheorem{conj}[thm]{Conjecture} \newtheorem{ques}[thm]{Question} \newtheorem{cons}[thm]{Construction} \theoremstyle{remark} \newtheorem*{rmk}{Remark} \newtheorem{case}{Case}[thm] \newtheorem{subcase}{Subcase}[case] %Commands \newcommand{\indsat}[2]{\ensuremath{\operatorname{indsat}(#1,#2)}\xspace} \newcommand{\sis}[2]{\ensuremath{{\operatorname{indsat}}^*(#1,#2)}\xspace} \newcommand{\sat}[2]{\ensuremath{\operatorname{sat}(#1,#2)}\xspace} \newcommand{\ex}[2]{\ensuremath{\operatorname{ex}(#1,#2)}\xspace} \newcommand{\claw}{\ensuremath{K_{1,3}}\xspace} \newcommand{\paw}{\ensuremath{K_{1,3}^+}\xspace} \newcommand{\Km}{$K^{(t_1,\ldots,t_{i-1})}$} \newcommand{\Kk}{$K^{(t_1,\ldots,t_{k-1})}$} \renewcommand{\bar}{\overline} \newcommand{\cl}[1]{\lceil#1\rceil} \newcommand{\CL}[1]{\left\lceil#1\right\rceil} \newcommand{\fl}[1]{\lfloor#1\rfloor} \newcommand{\FL}[1]{\left\lfloor#1\right\rfloor} \newcommand{\cartprod}{\mathop{\Box}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %title \title{Graphs with induced-saturation number zero} %author list \author{Sarah Behrens \thanks{Supported in part by National Science Foundation grant DMS-0914815.}\\ \small {Epic Systems Corporation}\\[-0.8ex] \small Wisconsin, U.S.A\\ \small\tt{sbehrens@epic.com} \and {Catherine Erbes}\thanks{Supported in part by National Science Foundation Grant DGE-0742434, UCD GK12 Transforming Experiences Project.} \\ \small Department of Mathematics\\[-0.8ex] \small {Hiram College}\\[-0.8ex] \small Ohio, U.S.A.\\ \small\tt{erbescc@hiram.edu} \and Michael Santana \thanks{The research of the third, fourth, and fifth authors is supported in part by National Science Foundation grant DMS 08-38434 ``EMSW21-MCTP: Research Experience for Graduate Students.''} \qquad Derrek Yager \\ \small Department of Mathematics\\[-0.8ex] \small University of Illinois at Urbana-Champaign\\[-0.8ex] \small Illinois, U.S.A.\\ \small\tt \{santana,yager2\}@illinois.edu \and Elyse Yeager\\ \small Department of Mathematics\\[-0.8ex] \small University of British Columbia\\[-0.8ex] \small British Columbia, Canada\\ \small\tt elyse@math.ubc.ca } %end authors list \date{\dateline{March 12, 2015}{Sept 28, 2015}\\ \small Mathematics Subject Classifications: 05C35, 05C75 } \begin{document} \maketitle %abstract \begin{abstract} Given graphs $G$ and $H$, $G$ is $H$-saturated if $H$ is not a subgraph of $G$, but for all $e \notin E(G)$, $H$ appears as a subgraph of $G + e$. While for every $n \ge |V(H)|$, there exists an $n$-vertex graph that is $H$-saturated, the same does not hold for induced subgraphs. That is, there exist graphs $H$ and values of $n \ge |V(H)|$, for which every $n$-vertex graph $G$ either contains $H$ as an induced subgraph, or there exists $e \notin E(G)$ such that $G + e$ does not contain $H$ as an induced subgraph. To circumvent this Martin and Smith \cite{MS} make use of a generalized notion of ``graph'' when introducing the concept of induced saturation and the induced saturation number of graphs. This allows for edges that can be included or excluded when searching for an induced copy of $H$, and the induced saturation number is the minimum number of such edges that are required. In this paper, we show that the induced saturation number of many common graphs is zero. This yields graphs that are $H$-induced-saturated. That is, graphs such that no induced copy of $H$ exists, but adding or deleting any edge creates an induced copy of $H$. We introduce a new parameter for such graphs, $\sis{n}{H}$, which is the minimum number of edges in an $H$-induced-saturated graph. We provide bounds on $\sis{n}{H}$ for many graphs. In particular, we determine $\sis{n}{H}$ completely when $H$ is the paw graph $K_{1,3}+e$, and we determine {$\sis{n}{\claw}$ within an additive constant of four.} \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Background and Introduction}\label{sec:intro} \subsection{Background and Definitions} A well-known graph parameter is the \emph{saturation number}, defined for a graph $H$ and a whole number $n$ as the minimum number of edges in a graph $G$ on $n$ vertices such that $H$ is not a subgraph of $G$, but $H$ occurs if any edge is added to $G$. Formally, \[\sat{n}{H}=\min\{|E(G)|:\text{G has~}n \text{~vertices}, H\not\subseteq G,\text{~and~}\forall e\notin E(G), H\subseteq G+e\}.\] Determining the saturation number for a given graph $H$ has proven, in general, quite difficult. For more information on the saturation number, see the dynamic survey of Faudree, Faudree, and Schmitt \cite{FFS}. A natural attempt at defining an induced variant of graph saturation would be to state that an $n$-vertex graph $G$ is $H$-induced-saturated if $G$ is $H$-free (that is, without $H$ as an induced subgraph) and for all $e \notin E(G)$, $G + e$ contains $H$ as an induced subgraph. Unfortunately, this is not always well-defined. That is, there exist graphs $H$ and values of $n \ge |V(H)|$ for which every $n$-vertex graph $G$ either contains $H$ as induced subgraph, or there exists $e \notin E(G)$ such that $G+e$ is $H$-free. A simple example is $n = 4$ and $H = \claw$. In this paper, we consider a variant of the saturation number introduced by Martin and Smith in 2012 that looks for induced copies of $H$, and considers deleting as well as adding edges. To create a well-defined parameter, Martin and Smith \cite{MS} make use of \emph{trigraphs}, objects also used by Chudnovsky and Seymour in their structure theorems on claw-free graphs \cite{CS}. \begin{defn} A \emph{trigraph} $T$ is a quadruple $(V(T), E_B(T), E_W(T), E_G(T))$, where $V(T)$ is the vertex set and the other three elements partition %${V(T)\choose 2}$ $\binom{V(T)}{2}$ into a set $E_B(T)$ of black edges, a set $E_W(T)$ of white edges, and a set $E_G(T)$ of gray edges. These can be thought of as edges, nonedges, and potential edges, respectively. For any $e\in E_B(T)\cup E_W(T),$ let $T_e$ denote the trigraph where $e$ is changed to a gray edge, i.e. $T_e=(V(T),E_B(T)-e,E_W(T)-e,E_G(T)+e)$. A \textit{realization} of $T$ is a graph $G=(V(G),E(G))$ with $V(G)=V(T)$ and $E(G)=E_B(T)\cup S$ for some $S\subseteq E_G(T)$. Let $\mathcal{R}(T)$ be the family of graphs that are a realization of $T$. A trigraph $T$ is \textit{$H$-induced-saturated} if no realization of $T$ contains $H$ as an induced subgraph, but $H$ occurs as an induced subgraph of some realization whenever any black or white edge of $T$ is changed to gray. The \textit{induced saturation number} of a graph %(or family of graphs) $H$ with respect to $n$, written $\indsat{n}{H}$, is the minimum number of gray edges in an $H$-induced-saturated trigraph with $n$ vertices. Formally, \begin{align*} \indsat{n}{H} = \min&\{|E_G(T)|:|V(T)|=n, \forall G\in \mathcal{R}(T), H\not\leq G,\\ &\text{and }\forall e\in E_B(T)\cup E_W(T), H\leq G', \text{ where } G'\in\mathcal{R}(T_e)\}.\\ \end{align*} %%%\refedits{Use align*- but.... just format it better (I agree)} Notice that a trigraph with $E_G(T)=\emptyset$ has a unique realization, so if $\indsat{n}{H}=0$, there is a graph $G$ that has no induced copy of $H$ yet adding or removing any edge creates an induced copy of $H$. We will call such a graph \textit{$H$-induced-saturated}. The {\it complement} of a trigraph $T$, denoted $\overline{T}$, is the trigraph with $V(\bar T)=V(T)$, $E_B(\overline{T}) = E_W(T)$, $E_W(\overline{T}) = E_B(T)$, and $E_G(\bar T)=E_G(T)$. \end{defn} %%%%\refedits{terms should be in italics instead of bold, except in a definition environment, where they should be Roman. (Problem: Whole thing from ``Def 1.1'' until next section is a definition environment!)} \subsection{Notation} A trivial component of a graph is an isolated vertex. For a graph $G$, we use $v(G)$ for the number of vertices and $e(G)$ for the number of edges in $G$. We let $P_n$ denote the path on $n$ vertices and $C_n$ the cycle on $n$ vertices. $K_n$ is the complete graph on $n$ vertices, and for $k \geq 2$, $K_{a_1,\ldots,a_k}$ is the complete multipartite graph with parts of size $a_1,\ldots,a_k$. $\paw$ is the paw, which is obtained by adding a single edge to $K_{1,3}$. For a set $S \subseteq V(G)$, $G[S]$ is the subgraph of $G$ induced by $S$, and if $S=\{v_1, \ldots, v_p\}$, we will sometimes write $G[v_1, \ldots, v_p]$. For a vertex $v\in V(G)$, $N_G(v)$ (or $N(v)$, if $G$ is clear from context) is the set of neighbors of $v$ in $G$, and $N[v]=N(v) \cup \{v\}$. We use $\deg_G(v)$ or $\deg(v)$ to denote the degree of $v$, that is, $|N(v)|$. In a trigraph, the black (resp. gray) degree of a vertex is the number of black (resp. gray) edges incident to that vertex. We say a set $S$ of vertices \emph{dominates} $G$, and we call $S$ a {\em dominating set}, if every vertex of $G-S$ is adjacent to some vertex in $S$; if $S=\{v\}$, we say $v$ is a \emph{dominating vertex}. Similarly, a vertex $u$ \emph{dominates} a vertex set $S$ if $u$ is adjacent to every vertex in $S$. For an integer $n$, we let $[n]=\{1,\ldots, n\}$. If $G$ and $H$ are graphs, then $G\cup H$ denotes their disjoint union. The graph $G \vee H$, known as the {\it join} of $G$ and $H$, is obtained by taking disjoint copies of $G$ and $H$ and making each vertex $u \in V(G)$ adjacent to each vertex $v \in V(H)$. The {\it Cartesian product} of $G$ and $H$, denoted $G \cartprod H$, is the graph with vertex set $V(G) \times V(H)$, where $(u_1, u_2)$ is adjacent to $(v_1,v_2)$ if either $u_1=v_1$ and $u_2$ is adjacent to $v_2$ in $H$, or if $u_2=v_2$ and $u_1$ is adjacent to $v_1$ in $G$. Other notation will be defined as it is used, or see \cite{West} for any undefined terms. \subsection{Observations and Previous Results} By definition, the only trigraphs on fewer than $v(H)$ vertices that are $H$-induced-saturated are those in which all edges are gray. Thus we will usually assume that $n \ge v(H)$ when we discuss $\indsat{n}{H}$. The following theorem summarizes the results of Martin and Smith~\cite{MS}: \begin{thm}\label{thm:sat} Let $H$ be a graph. \begin{itemize} \item For all $n\geq v(H)$, $\indsat{n}{H}\leq\sat{n}{H}$. By~\cite{KT}, $\sat{n}{H} =O(n)$, so in particular $\indsat{n}{H}= O(n)$. \item For all $n\geq m\geq3$, $\indsat{n}{K_m}=\sat{n}{K_m}$. (Note that $\sat{n}{K_m}$ was determined by Erd\H{o}s, Hajnal, and Moon in \cite{EHM}.) \item For all $n\geq m\ge 2$, and for $e \in E(K_m)$, $\indsat{n}{K_m-e}=0$. In particular, for all $n\geq3$, $\indsat{n}{P_3}=0$. \item For all $n\geq4$, $\indsat{n}{P_4}=\left\lceil\frac{n+1}{3}\right\rceil$. \end{itemize} \end{thm} We also make the following observation, which was stated in \cite{MS} for $H=P_4$: \begin{obs}\label{thm:complement} A trigraph $T$ is $H$-induced-saturated if and only if $\bar T$ is $\bar H$-induced-saturated. In particular, $\indsat{n}{H}=\indsat{n}{\overline{H}}$. \end{obs} \begin{proof} Suppose a trigraph $T$ has a realization $G$ such that $H$ is an induced subgraph of $G$. Then $\bar H$ is an induced subgraph of $\bar G$. Using the definition of $\bar T$, $\bar G$ is a representation of $\bar T$. It follows that a trigraph $T$ is $H$-induced-saturated if and only if $\bar T$ is $\bar H$-induced-saturated. \end{proof} \subsection{Minimally \emph{H}-induced-saturated Graphs} In this paper we show that $\indsat{n}{H}$ is zero for several graphs, which as noted above, means that there exists a graph that is $H$-induced-saturated. This leads to the natural question: What is the minimum number of edges in such a graph? \begin{defn} For a graph $H$ and whole number $n$ with $\indsat{n}{H}=0$, we define $$\sis{n}{H}:=\min\{e(G):v(G)=n \text{ and }G\text{ is }H\text{-induced-saturated}\}.$$ We say a graph $G$ on $n$ vertices with $\sis{n}{H}$ edges is {\bf minimally $H$-induced-saturated}.\end{defn} By Observation \ref{thm:complement}, the \emph{maximum} number of edges in an $n$-vertex\\ $H$-induced-saturated graph is $\binom{n}{2} - \sis{n}{\overline H}$. %In this paper we will show that the following graphs have induced-saturation number zero for $n$ sufficiently large: $\paw$, stars $K_{1,t}$, $C_4$, odd cycles, some modifications of even cycles, and matchings. % all have induced-saturation number 0. %%In some cases, the construction of a graph that is $H$-induced-saturated also yields the value of $\sis{n}{H}$, and in other cases determining this value is more complicated. %Additionally, we provide bounds on $\sis{n}{H}$ for the graphs listed above. In particular, we characterize the $\paw$-induced-saturated graphs, which in turn completely determines $\sis{n}{\paw}$. We also determine $\sis{n}{K_{1,t}}$ within a factor of 2 and show that the upper bound is correct for $K_{1,3}$. Finally, we introduce the induced-saturation number of a family of graphs and show that while every graph in a family may have induced-saturation number zero, the family itself could have nonzero induced-saturation number. %\refedits{Give a detailed description of which results are in which sections, so one can find the result one needs} The paper proceeds as follows. In Section \ref{sec:paw}, we characterize the\\ $\paw$-induced-saturated graphs, which in turn completely determines $\sis{n}{\paw}$. Section \ref{sec:stars} contains a construction that shows that $\indsat{n}{H}=0$ when $H$ is a star, and gives bounds on $\sis{n}{H}$ for stars. Section \ref{sec:claw} studies $\sis{n}{\claw}$ in detail, showing that the upper bound given in Section \ref{sec:stars} is correct for $\claw$. In Section \ref{sec:small cycles}, we turn our attention to $C_4$, proving that $\indsat{n}{C_4}=0$ and giving an upper bound on $\sis{n}{C_4}$. We also use the complement of $C_4$ to show that $\indsat{n}{kK_2} = 0$ with a constant upper bound on $\sis{n}{kK_2}$. Section \ref{sec:weird cycles} gives an upper bound on $\sis{n}{H}$ when $H$ is an odd cycle or a minor modification of an even cycle. Finally, in Section \ref{sec:families}, we introduce the induced-saturation number of a family of graphs and show that while every graph in a family may have induced-saturation number zero, the family itself could have nonzero induced-saturation number. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % PAW % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Paw}\label{sec:paw} %In this section we characterize the \paw-induced saturated graphs on at least seven vertices, which allows us to completely determine $\sis{n}{\paw}$ for $n \ge 7$. In this section we will prove the following theorem, which will allow us to completely determine $\sis{n}{\paw}$ for $n \ge 7$. \begin{thm}\label{paw_unique} A graph is \paw-induced-saturated if and only if it is as described in Construction \ref{cons:paw}. \end{thm} %REORG:In this section we provide a construction that shows $\indsat{n}{\paw} = 0$ for $n \ge 7$. We then show that our construction characterizes all $\paw$-induced-saturated graphs, allowing us to completely determine $\sis{n}{\paw}$ for $n \ge 7$. The graphs in Construction \ref{cons:paw} do not exist for $n < 7$, and as Theorem \ref{paw_unique} shows that these are the only $\paw$-induced-saturated graphs, it follows that $\indsat{n}{\paw}$ is nonzero for $n \in \{4,5,6\}$. %REORG:This construction, given in Construction \ref{cons:paw} below, requires $n \ge 7$. Theorem \ref{paw_unique} will show that these are the only $\paw$-induced-saturated graphs, so we deduce that $\indsat{n}{\paw}$ is nonzero for $n \in \{4,5,6\}$. The exact values for such $n$ are provided in Table \ref{tab:paw}. In this table, we see that for $n \in \{5,6\}$, there are \paw-induced-saturated trigraphs on $n$ vertices that have only one gray edge. This establishes $\indsat{n}{\paw}=1$ for such $n$. For $n=4$, we have a 4-vertex, \paw-induced-saturated trigraph with two gray edges. To show that $\indsat{4}{\paw} = 2$, we argue that any 4-vertex trigraph with only one gray edge is not \paw-induced-saturated. Suppose $T$ is a \paw-induced-saturated trigraph on 4 vertices with one gray edge. Clearly, $T$ has at least two black edges, otherwise changing a white edge to gray does not result in a realization with an induced \paw. Now suppose $T$ has no white edges. Since it has precisely one gray edge, its black edges form $K_4-e$, and changing the black edge whose endpoints have black degree three to a gray edge does not result in a realization with an induced \paw. Next, suppose $T$ has at least two white edges. Since \paw has precisely two nonedges, changing a black edge to gray does not result in a realization with an induced \paw, unless $T$ already had such a realization. Therefore $T$ has precisely one white edge. If the gray edge of $T$ is incident to the white edge, then \paw is a realization, so the black edges induce $C_4$. Since $C_4 \not\subseteq \paw$, changing the white edge to gray does not create an induced \paw. Thus, this trigraph does not exist, and $\indsat{4}{\paw}=2$. %The black and gray edges of $T$ properly contain \paw, so there can be at most one white edge. %If there is a white edge, then the black edges form $C_4$ or $K_4-e$. %Either way, the black edges contain $C_4$, which does not appear in an induced \paw. %Therefore we cannot add an edge to obtain a \paw. %Thus, there must be no white edges. If there is only one gray edge, then the black edges form $K_4-e$. %However, changing the black edge whose endpoints have black degree three to a gray edge does not result in a realization with an induced paw. %The first graph in \hyperref[tab:paw]{Table \ref*{tab:paw}} shows that this is also an upper bound. %Simple arguments show that the trigraphs displayed in \hyperref[tab:paw]{Table \ref*{tab:paw}} are \paw-induced-saturated. \begin{table}[h]%[htp] \newcolumntype{S}{>{\centering\arraybackslash} m{.23\linewidth} } \newcolumntype{T}{>{\centering\arraybackslash} m{.26\linewidth} } \centering %\captionsetup{labelformat=empty, labelsep=none, textformat=empty} \caption{Values of $\indsat{n}{\paw}$ for $4\leq n\leq6$ and trigraphs realizing those values} \label{tab:paw} \begin{tabular}{S|T} \ & trigraph\\ \hline \\[-2ex] %\noalign{\smallskip} \ $\indsat{4}{\paw}=2$ & \begin{tikzpicture} \node at (0,0) [vx](1){}; \node at (0,.75) [vx](0){}; \node at (-1.25,-.5) [vx](2){}; \node at (1.25,-.5) [vx](3){}; \draw (0)--(2)--(1)--(3)--(0); \draw[grayedge] (0)--(1); \draw[grayedge] (2)--(3); \end{tikzpicture} \\ \hline \\[-2ex] \ $\indsat{5}{\paw}=1$ & %\includegraphics[scale=.2, trim= 0 0 0 .2cm, clip=true]{figures/paw_5.png} \begin{tikzpicture} \node at (0,0) [vx](2){}; \node at (1,0) [vx](3){}; \node at (2,0) [vx](4){}; \node at (-1,1) [vx](0){}; \node at (-1,-1)[vx](1){}; \foreach \x in {2,3,4}{\draw (0)--(\x)--(1);} \draw[grayedge] (0)--(1); \end{tikzpicture}\\ \hline \\[-2ex] \ $\indsat{6}{\paw}=1$ & %\includegraphics[scale=.2, trim= 0 0 0 .2cm, clip=true]{figures/paw_6.png} \begin{tikzpicture}[scale=0.8] \node at (0,0) [vx](2){}; \node at (1,0) [vx](3){}; \node at (2,0) [vx](4){}; \node at (3,0) [vx](5){}; \node at (-1,1) [vx](0){}; \node at (-1,-1)[vx](1){}; \foreach \x in {2,3,4,5}{\draw (0)--(\x)--(1);} \draw[grayedge] (0)--(1); \end{tikzpicture} \\ \end{tabular} \end{table} Having established $\indsat{n}{\paw}$ for small values of $n$, we now present our construction. \begin{cons}\label{cons:paw} Let $G$ be a graph with at most one trivial component, where each nontrivial component is complete multipartite. Further, each nontrivial component has at least three parts, at most one of which contains only one vertex, and the remainder of which have order at least three. \end{cons} Notice that graphs such as those in Construction \ref{cons:paw} exist for all $n \ge 7$. In particular, any complete tripartite graph with parts of the appropriate order will suffice. %\refedits{Should mention that construction 2.1 exists for all $n \ge 7$} \begin{prop} The graph $G$ in Construction \ref{cons:paw} is \paw-induced-saturated. \end{prop} \begin{proof} Since \paw is not an induced subgraph of a complete multipartite graph, $G$ contains no induced \paw. Suppose we add an edge $xy$ such that $x$ and $y$ are in distinct components, say $F_x$ and $F_y$, respectively. Since at least one of these components, say $F_x$, has at least three parts, $x$ is in some triangle $xab$ in $F_x$. Because $y$ is in a different component, $y$ is adjacent to $x$ but not $a$ or $b$. Thus $\{x,y,a,b\}$ induces a \paw. Suppose we add an edge $xy$ such that $x$ and $y$ are in the same component. Then in particular, they are in the same part. This part has at least two vertices, so by construction it has at least three vertices; choose $z$ distinct from $x$ and $y$ from this part, and let $a$ be in another part of the component. Then $\{x,y,z,a\}$ induces a \paw. Suppose we delete an edge $xy$. Then $x$ and $y$ were in different parts of one component, say $F$. As $F$ is complete multipartite with at least three parts, there exists a vertex $z$ in a third part of that component. Since at most one part has only one vertex, there is a vertex $a$ in the same part as either $x$ or $y$; say $x$. Then $\{x,y,z,a\}$ induces a \paw. \end{proof} The induced-saturation number $\indsat{n}{\paw}$ is an immediate corollary of this result. \begin{cor}\label{indsat_paw} For $n \ge 7$, $\indsat{n}{\paw}=0$. \end{cor} %We now show that Construction~\ref{cons:paw} describes all \paw-induced-saturated graphs. To Since $\indsat{n}{\paw}=0$ for $n \ge 7$, we turn our attention to Theorem \ref{paw_unique}, which will allow us to determine $\sis{n}{\paw}$. To prove the theorem, we begin by making several observations. %REORG %\begin{thm}\label{paw_unique} %A graph is \paw-induced-saturated if and only if it is as described in Construction \ref{cons:paw}. %\end{thm} %To prove this theorem, we begin by making several observations. \begin{lem}\label{lem:paw_obs} Let $G$ be a \paw-induced-saturated graph. Then $G$ has the following properties: \begin{enumerate}[label=(\alph*), ref=\ref{lem:paw_obs}(\alph*)] %\item\label{K_4-e} Any edge of $G$ is in an induced copy of $K_4-e$. \item\label{triangle} Every edge of $G$ is in a triangle. \item\label{multipartite} The neighborhood of any vertex of $G$ is a complete multipartite graph. \item\label{book} Given any non-isolated vertex $v \in V(G)$, the set $N(x)\setminus N[v]$ is the same for every $x \in N(v)$. Call this set $S(v)$. If $S(v)$ is not empty, then $S(v)$ is an independent set. %there exists a (possibly empty) independent set $S=S(v)$ such that for every $x \in N(v)$, $S = N(x) \setminus N[v]$. \refedits{Don't like the phrasing (gives suggestions)} \end{enumerate} \end{lem} \begin{proof} Lemma~\ref{triangle} holds because deleting any edge in $G$ creates an induced \paw. As a consequence, any vertex has either degree zero or degree at least two. Since $G$ does not contain an induced $\paw$, the neighborhood of any vertex cannot contain an induced copy of $K_2 \cup K_1$. This is equivalent to the neighborhood being a complete multipartite graph. This gives us Lemma~\ref{multipartite}. To prove Lemma~\ref{book}, suppose there exists $x \in N(v)$ that has a neighbor not in $N[v]$. (If no such $x$ exists, the claim holds with $S = \emptyset$.) Let $S:=N(x) \setminus N[v]$. If $G[S]$ has an edge $ss'$, then $G[v,x,s,s']$ is a \paw. Since $G$ is \paw-induced-saturated, we conclude that $S$ is independent. By Lemma~\ref{triangle}, there exists $y \in N(v) \cap N(x)$. If any element $s \in S$ is not adjacent to $y$, then $G[v,x,y,s]$ is a \paw with $s$ as the pendant vertex. Therefore, $S \subseteq N(y)$, but also $N(y)\backslash N[v]\subseteq S$ or else we would have a \paw. Because $N(v)$ is complete multipartite by Lemma~\ref{multipartite}, every vertex in $N(v)\setminus\{x,y\}$ is adjacent to $x$ or $y$. By symmetry, we conclude that for every $z \in N(v)$, $N(z)\setminus N[v] = S$. \end{proof} We proceed to the proof of Theorem~\ref{paw_unique}. \begin{proof}[Proof of Theorem~\ref{paw_unique}] Let $G$ be a \paw-induced-saturated graph. It is clear that $G$ has at most one nontrivial component, since adding an edge between two isolated vertices does not create an induced $\paw$. We now show that every nontrivial component of $G$ is a complete multipartite graph. Let $v$ be a non-isolated vertex in $G$ and let $S$ be the set given by Lemma~\ref{book}. By Lemmas~\ref{multipartite} and \ref{book}, $G[N[v] \cup S]$ is a complete multipartite graph, with $v$ and $S$ sharing a part. So, we need only show $N[v] \cup S$ is a component of $G$. If not, then there exists some vertex $s \in S$ with a neighbor $t \not\in N[v]\cup S$ since we have included the neighborhood of every $x\in N[v]$ and $S$ is an independent set. If there exists an edge $xy$ in $G[N(v)]$, then $G[x,y,s,t]$ is a \paw, so $N(v)$ is an independent set. This violates Lemma~\ref{triangle}. Now, by Lemma~\ref{triangle}, every nontrivial component of $G$ must have at least three parts. Next, we show that no part in any component of $G$ has order two, and each component has at most one parts of order one. %\refedits{I think you cannot have two parts of order one (phrased wrong)}. Suppose $x$ and $y$ either make up a part of order two, or are each a part of order one in a component $F$. Then $\{x,y\}$ dominates $F\setminus\{x,y\}$, and so $x$ and $y$ do not appear together in an induced claw, %\refedits{I think this is a claw (?)}, so adding or deleting the edge $xy$ does not create an induced paw. Hence, $G$ being \paw-induced-saturated implies that it must be as described by Construction \ref{cons:paw}. \end{proof} %\subsubsection{$\sis{n}{\paw}$, $\sis{n}{P_3+K_1}$} \begin{cor}\label{sis paw}For $n \geq 7$, let $n\equiv r \mod 7$, where $0 \le r \le 6$. Then %$15p \leq \sis{n}{\paw} \leq 15p+20$ and %for $n \geq 35$, \begin{equation*}\sis{n}{\paw} = \left\{ \begin{array}{cl}\displaystyle\frac{15}{7}n & \mbox{ if } r =0\\ 15\lfloor n/7\rfloor+4(r-1) & \mbox{ if } r \neq 0\end{array} \right..\end{equation*} % For $n \geq 7$, let $n = 3q+s$ for $0 \le s \le 2$. Then %\begin{equation*}\sis{n}{P_3+K_1} = \left\{ %\begin{array}{cl}3q & \mbox{ if } s \neq 2\\ %3(q+1) & \mbox{ if } s =2\end{array} %\right..\end{equation*} \end{cor} \begin{proof} Let $G$ be a minimally \paw-induced-saturated graph on $n$ vertices. From Theorem \ref{paw_unique}, each nontrivial component of $G$ is a complete multipartite graph with at least three parts. If some nontrivial component $F$ of $G$ has more than three parts, then we form a \paw-induced-saturated graph with strictly fewer edges by dropping edges between two of the parts and forming a single larger part. % Let $a_1, a_2, \ldots,a_k$ be the size of the parts, in nondecreasing order. %Then replacing $F$ with $K_{a_1,a_2,\ldots,a_{k-2},a_{k-1}+a_k}$ yields a \paw-induced-saturated graph with fewer edges. Thus each nontrivial component of $G$ is tripartite. The number of edges of a complete tripartite graph on $m$ vertices with parts of size $s,t,$ and $m-(s+t)$ is given by $(m-[s+t])(s+t)+st$. Given the constraints $s\geq1, t\geq3$, and $m\geq t$, we see that $(m-(s+t))(s+t)$ is minimized when $s+t$ is minimized, i.e. $s+t=4$; also $st$ is minimized when $s+t$ is minimized. Therefore, $K_{1,3,m-4}$ obtains the smallest number of edges among all complete tripartite graphs on $m$ vertices. Now, we may assume $G$ has components $F_0,F_1,\ldots,F_k$ with $v(F_0) \in \{0,1\}$ and for $i>0$, $F_i=K_{1,3,n_i-4}$, where $v(F_0)+\sum_{i=1}^kn_i=n$. Then: $$e(G) = \sum_{i=1}^k e(F_i)= \sum_{i=1}^k (4n_i-13)= 4n-13k-4v(F_0).$$ Clearly, this is minimized by taking $k$ as big as possible and, subject to this, $v(F_0)=1$. That is, we take $k=\lfloor n/7 \rfloor$ and \begin{displaymath}v(F_0)=\left\{\begin{array}{rl} 0 & \mbox{ if 7 divides $n$}\\ 1 & \mbox{ else.} \end{array} \right. \end{displaymath} \end{proof} \begin{obs} Given $H$ for which $\sis{n}{H}$ is defined for all sufficiently large $n$, the function $\sis{n}{H}$ is not necessarily monotone in $n$. In particular, from Corollary~\ref{sis paw} we see for any integer $k \geq 2$, $\sis{7k}{\paw}<\sis{7k+2}{\paw}<\sis{7k-1}{\paw}$. This is a similarity between minimal induced saturation and saturation: as noted in~\cite{FFS}, the function $\sat{n}{H}$ is not necessarily monotone in $n$ for fixed $H$. \end{obs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % STARS % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %begin subsection stars \section{Stars}\label{sec:stars} Recall that $K_{1,2} = P_3$, and $\indsat{n}{P_3} = 0$ for $n \ge 3$, as established in \cite{MS}. In this section we provide a construction extending this result, to show that for fixed $k \ge 2$ and $n$ sufficiently large, $\indsat{n}{K_{1,k+1}}=0$. Additionally, our construction, together with a simple argument, determines $\sis{n}{K_{1,k+1}}$ within a factor of two. The main result of this section is Theorem \ref{bound:stars}, which gives the bounds on $\sis{n}{K_{1,k+1}}$. The case when $k = 2$, which refers to the graph $K_{1,3}$, commonly known as the claw, will be addressed in further detail in Section \ref{sec:claw}. \begin{cons}\label{cons:stars} Fix $k \ge 2$ and $n \ge 3^k$. Let $z,R$ be positive integers such that $n = z3^k + R$ with $0 \le R < 3^k$. Let $H$ be the graph $K_3^1 \cartprod K_3^2 \cartprod \cdots \cartprod K_3^k$, where $K_3^i$ denotes a single copy of $K_3$. In other words, $V(H) = \{(\alpha_1,\dots, \alpha_k) : \alpha_i \in [3]\}$, and $(\alpha_1,\dots, \alpha_k)(\beta_1,\dots, \beta_k) \in E(H)$ if and only if $ |\{i:\alpha_i\neq\beta_i\}| = 1$. %\refedits{Weird sentence structure} Let $H'$ be such that $V(H')$ is the disjoint union of $V(H)$ and $V(K_R)$, and $E(H')=E(K_R)\cup E(H) \cup \{v \alpha : v \in V(K_R), \alpha \in V(H), \text{ and } \alpha=(\alpha_1, 1,1,\ldots,1) \text { where } \alpha_1 \in [3]\}$. % consists of $E(H),$ $E(K_R)$ and the edges between $H$ and $K_R$ satisfy: for each $v \in V(K_R)$, $v\alpha \in E(H')$ if and only if $\alpha = (\alpha_1,1,1,\dots,1)$, $\alpha_1 \in [3]$. Let $G$ be the disjoint union of $z-1$ copies of $H$ and a single copy of $H'$. \end{cons} \begin{prop}\label{prop:stars2} The graphs in Construction \ref{cons:stars} are $K_{1,k+1}$-induced-saturated. \end{prop} \begin{proof} Given fixed $n$ and $k$, let $G$ and $R$ be as defined in Construction \ref{cons:stars}. Let $F$ denote the subgraph of $H'$ isomorphic to $H$. Suppose that $G$ contains an induced $K_{1,k+1}$ with center $x$, and suppose first that $x$ is in a copy of $H$. Since $V(G)$ can be represented by $k$-dimensional vectors as described in the construction, any set of $k+1$ neighbors of $x$ contains two vertices with vectors that differ in exactly one coordinate. Thus, $x$ cannot have $k+1$ neighbors which form an independent set, and $H$ is $K_{1,k+1}$-free. If $H'$ contains an induced $K_{1,k+1}$, then $x$ cannot be in the $K_R$ as the neighborhood of $x$ would be a clique. Thus, $x$ is in $F$. If this induced $K_{1,k+1}$ contains no vertices from the copy of $K_R$, then the above argument produces a contradiction. Thus, this $K_{1,k+1}$ contains a vertex from the copy of $K_R$, and without loss of generality, we may assume that $x$ is represented by $(1,1,\dots,1)$ in $F$. Consequently, our $K_{1,k+1}$ has exactly one vertex in $K_R$, but then contains no vertices of the form $(\alpha_1,1,1,\dots,1)$ other than $x$. Hence, $x$ has at most $k-1$ other neighbors from $F$ in this copy of $K_{1,k+1}$ from $F$. So $G$ is $K_{1,k+1}$-free. It is clear that every vertex in a copy of $H$ (or in $F$) is the center of an induced $K_{1,k}$. Thus, if we add an edge between two components of $G$, one component must be a copy of $H$, and we obtain an induced $K_{1,k+1}$. Thus, it remains to consider adding an edge within a component. Note that by the construction of $H'$, the only possible way to add an edge is within $F$, which is isomorphic to $H$. So, it suffices to consider adding an edge to a copy of $H$. Suppose we add the edge $uv$. Without loss of generality, we may assume that $u$ is represented by $(1,1,\dots, 1)$. Since $u$ and $v$ were not adjacent in $H$, their corresponding vectors must differ in at least two coordinates, say the first and second. As a consequence, $v$ is adjacent to neither $y$ nor $w$, where $y \in \{(2,1,1,\dots,1), (3,1,1,\dots,1)\}$ and $w \in \{(1,2,1,1,\dots,1), (1,3,1,1,\dots,1)\}$. Thus, $\{u,v,w,y\}$ is an induced $K_{1,3}$ centered at $u$. To this set we add vertices $\alpha^3,\alpha^4,\dots, \alpha^k$, where $\alpha^i$ has all coordinates equal to 1 except that the $i$th coordinate is either 2 or 3. This induces $K_{1,k+1}$. Lastly, suppose we remove an edge $uv$. There are three cases to consider. The first case is if $uv$ is in a copy of $H$ (or in $F$). Here, we may assume $u = (2,1,1,\dots,1)$ and $v = (3,1,1,\dots,1)$. The second case is if both $u$ and $v$ are in $K_R$. The last case is if only endpoint, say $v$, is in $K_R$. Here, we may again assume that $u = (2,1,1,\dots,1)$. In all three cases, $(1,1,\dots,1)$ together with $u,v$, and the vertices $\alpha^2,\dots,\alpha^k$ defined above induce a $K_{1,k+1}$. This completes the proof. \end{proof} %} \begin{cor}\label{cor:stars} For fixed $k \ge 2$ and $n \ge 3^k$, $\indsat{n}{K_{1,k+1}} = 0$. \end{cor} %Theorem \ref{prop:stars} is an immediate corollary of Lemmas~\ref{lem:stars1} and \ref{lem:stars2}. %Furthermore, we can show that $\sis{n}{K_{1,k+1}}$ is linear in $n$ for fixed $k \geq 2$ and sufficiently large $n$. \begin{thm}\label{bound:stars} For $n \geq 2\cdot 3^k$ and $k \geq 2$, there exist constants $c_1=c_1(k)$ and $c_2 = c_2(k)$ such that $n\frac{k}{2} - c_1 \le \sis{n}{K_{1,k+1}} \leq nk+c_2$. \end{thm} \begin{proof} Given fixed $n$ and $k$, let $G$ and $R$ be as defined in Construction \ref{cons:stars}. We establish $e(G)$ by considering vertex degrees. The component $H'$ has at most $2\cdot 3^k$ vertices, and so (trivially) at most % ${2\cdot 3^k \choose 2}$ $\binom{2\cdot 3^k}{2}$ edges. The remaining vertices, of which there are at most $n-3^k$, all have degree $2k$ for a contribution of at most $(n-3^k)k$ edges. All told, $e(G) \leq nk-k\cdot 3^k + \binom{2\cdot 3^k}{2}$. To show the lower bound, suppose that $G$ is a $K_{1,k+1}$-induced-saturated graph. Let $S=\{x \in V(G) \colon \deg(x) \le k-1\}$. %\subseteq V(G)$ be the set of vertices such that for all $x \in S$, $\deg(x) \le k - 1$. We claim that $|S| \le k$. If $|S| > k$, then there exist $x,y \in S$ such that $xy \notin E(G)$. Let $G'$ denote $G + xy$. As $G$ was $K_{1,k+1}$-induced-saturated, $G'$ must contain an induced $K_{1,k+1}$, using the edge $xy$ with either $x$ or $y$ as the center of this $K_{1,k+1}$. However, as both $x$ and $y$ are adjacent to at most $k - 1$ vertices in $G$, this cannot happen. So $|S| \le k$, as claimed. Observe: $$ e(G) \ge \frac{1}{2}\left(k(n - |S|) + \sum\limits_{x \in S} \deg(x)\right) \ge \frac{nk}{2} - \frac{k^2}{2}.$$ This establishes the lower bound. \end{proof} It worth noting that we can extend Construction \ref{cons:stars}, as any graph formed as a Cartesian product of exactly $k$ cliques, each of size at least three, is $K_{1,k+1}$-induced-saturated. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % CLAW % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %begin subsection claw \section{The Claw}\label{sec:claw} %\todo[inline, color=yellow]{Fact that is used often, but only formally stated in one proof: Let $G$ be a \claw-induced-saturated graph. When edge $xy$ is added, eith $x$ or $y$ is the center of an induced \claw. When edge $xy$ is removed, both $x$ and $y$ are leaves of an induced \claw.} For sufficiently large $n$, Theorem \ref{bound:stars} states that $\sis{n}{K_{1,k+1}}$ is linear in $n$, and in particular, we know the coefficient within a factor of two. %In this section, we will determine the coefficient of $\sis{n}{K_{1,3}}$, which coincides with the upper bound given in Theorem \ref{bound:stars}. Additionally, we will provide better constructions than that in Construction \ref{cons:stars}, which will ultimately determine $\sis{n}{K_{1,3}}$ within an additive constant of four. In this section, we will prove the following theorem, which agrees with the upper bound given in Theorem \ref{bound:stars} and further narrows the range of possible values of $\sis{n}{\claw}$. \begin{thm}\label{thm:claw-sis} For $n \ge 9$, if $n \neq 14, 17$, then $2n - 2 \le \sis{n}{K_{1,3}} \le 2n + 2$. \end{thm} Values of $\indsat{n}{\claw}$ were determined for $4\leq n \leq 10$ by computer search\footnote{A program was written in C++ and is available at \url{http://www.math.unl.edu/~s-sbehren7/main/Data.html}.} and are listed in \hyperref[tab:claws]{Table~\ref*{tab:claws}}, along with trigraphs that achieve the minimum number of gray edges. This together with Corollary \ref{cor:stars} determines $\indsat{n}{\claw}$ for all $n$. We now turn our attention to $\sis{n}{\claw}$. \begin{table}[htp] \newcolumntype{V}[1]{>{\centering\arraybackslash} m{#1\linewidth} } \centering \begin{tabular}{|c||c|} \hline %\\[-2ex] %\captionsetup{labelformat=empty, labelsep=none, textformat=empty} \begin{tabular}{V{.205}|V{.2}} %\hline \\[-2ex] $\indsat{4}{\claw}=3$ & \begin{tikzpicture}[scale=.75] \node at (1,1) [vx, scale=.75](0){}; \node at (0,0) [vx, scale=.75](1){}; \node at (2,0) [vx, scale=.75](2){}; \node at (3,.5) [vx, scale=.75](3){}; \draw[sgrayedge] (0)--(1)--(2)--(0); \end{tikzpicture} \\ \hline \\[-2ex] $\indsat{5}{\claw}=3$ & \begin{tikzpicture}[scale=.75] \node at (1,1) [vx, scale=.75](0){}; \node at (0,0) [vx, scale=.75](1){}; \node at (2,0) [vx, scale=.75](2){}; \node at (3,.5) [vx, scale=.75](3){}; \node at (4,.5)[vx, scale=.75](4){}; \draw[sgrayedge] (0)--(2)--(3)--(0); \draw (0)--(1)--(2); \end{tikzpicture} \\ \hline \\[-2ex] $\indsat{6}{\claw}=3$ & \begin{tikzpicture}[scale=.75] \node at (0,0) [vx, scale=.75](0){}; \node at (1,.75) [vx, scale=.75](1){}; \node at (1,-.75)[vx, scale=.75](2){}; \node at (2,0)[vx, scale=.75](3){}; \node at (3,0)[vx, scale=.75](4){}; \node at (4,0)[vx, scale=.75](5){}; \draw (0)--(1)--(3)--(2)--(0)--(3); \draw[sgrayedge] (1)--(2)--(4)--(1); \end{tikzpicture} \\ \hline \\[-2ex] $\indsat{7}{\claw}=2$& \begin{tikzpicture} \node at (0,0)[vx, scale=.75](0){}; \node at (1,0)[vx, scale=.75](1){}; \node at (2,0)[vx, scale=.75](2){}; \node at (.5,.5)[vx, scale=.75](3){}; \node at (1.5,.5)[vx, scale=.75](4){}; \node at (.5,-.5)[vx, scale=.75](5){}; \node at (1.5,-.5)[vx, scale=.75](6){}; \draw (0)--(3)--(4)--(2)--(6)--(5)--(0); \draw (3)--(1)--(5); \draw (4)--(1)--(6); \draw[sgrayedge] (3)--(5); \draw[sgrayedge] (4)--(6); \end{tikzpicture}\\ \hline \\[-2ex] $\indsat{8}{\claw}=2$& \begin{tikzpicture} \node at (0,0)[vx, scale=.75](0){}; \node at (1,0)[vx, scale=.75](1){}; \node at (2,0)[vx, scale=.75](2){}; \node at (.5,.5)[vx, scale=.75](3){}; \node at (1.5,.5)[vx, scale=.75](4){}; \node at (.5,-.5)[vx, scale=.75](5){}; \node at (1.5,-.5)[vx, scale=.75](6){}; \draw (0)--(3)--(4)--(2)--(6)--(5)--(0); \draw (3)--(1)--(5); \draw (4)--(1)--(6); \draw[sgrayedge] (3)--(5); \draw[sgrayedge] (4)--(6); \node at (2.75,0)[vx, scale=.75](7){}; \end{tikzpicture} \\ \hline\\[-2ex] $\indsat{9}{\claw}=0$& \begin{tikzpicture}[xscale=.75, yscale=.5] \node at (0,0)[vx, scale=.75](0){}; \node at (1,.5)[vx, scale=.75](1){}; \node at (2,0)[vx, scale=.75](2){}; \node at (.5,1)[vx, scale=.75](3){}; \node at (1.5,1.5)[vx, scale=.75](4){}; \node at (2.5,1)[vx, scale=.75](5){}; \node at (0,2)[vx, scale=.75](6){}; \node at (1,2.5)[vx, scale=.75](7){}; \node at (2,2)[vx, scale=.75](8){}; \draw (0)--(1)--(2)--(0); \draw (3)--(4)--(5)--(3); \draw (6)--(7)--(8)--(6); \draw (0)--(3)--(6)--(0); \draw (1)--(4)--(7)--(1); \draw (2)--(5)--(8)--(2); \end{tikzpicture} \\ %\hline \end{tabular} &\begin{tabular}{V{.22}|V{.19}} %\hline\\[-2ex] \multirow{5}{*}{$\indsat{10}{\claw}=0$} & \begin{tikzpicture}[xscale=.75, yscale=.5] \clip (-.25,-.25) rectangle (3.5, 2.5cm + 2ex); %\draw[help lines,step=.25cm] (-.25,-.5) grid (4.25, 3.5); %\draw[help lines,thick,step=1] (0,0) grid (4, 3); \node at (0,0)[vx, scale=.75](0){}; \node at (1,.5)[vx, scale=.75](1){}; \node at (2,0)[vx, scale=.75](2){}; \node at (.5,1)[vx, scale=.75](3){}; \node at (1.5,1.5)[vx, scale=.75](4){}; \node at (2.5,1)[vx, scale=.75](5){}; \node at (0,2)[vx, scale=.75](6){}; \node at (1,2.5)[vx, scale=.75](7){}; \node at (2,2)[vx, scale=.75](8){}; \node at (3.25,1)[vx, scale=.75](9){}; \draw (0)--(1)--(2)--(0); \draw (3)--(4)--(5)--(3); \draw (6)--(7)--(8)--(6); \draw (0)--(3)--(6)--(0); \draw (1)--(4)--(7)--(1); \draw (2)--(5)--(8)--(2); \end{tikzpicture} \\ \cline{2-2}\\[-2ex] &\begin{tikzpicture}[xscale=.75, yscale=.5] \node at (0,0)[vx, scale=.75](0){}; \node at (1,.5)[vx, scale=.75](1){}; \node at (2,0)[vx, scale=.75](2){}; \node at (.5,1)[vx, scale=.75](3){}; \node at (1.5,1.5)[vx, scale=.75](4){}; \node at (2.5,1)[vx, scale=.75](5){}; \node at (0,2)[vx, scale=.75](6){}; \node at (1,2.5)[vx, scale=.75](7){}; \node at (2,2)[vx, scale=.75](8){}; \node at (3.25,1)[vx, scale=.75](9){}; \draw (0)--(1)--(2)--(0); \draw (3)--(4)--(5)--(3); \draw (6)--(7)--(8)--(6); \draw (0)--(3)--(6)--(0); \draw (1)--(4)--(7)--(1); \draw (2)--(5)--(8)--(2); \foreach \x in {2,5,8} {\draw (9)--(\x);} \end{tikzpicture} \\ \cline{2-2}\\[-2ex] &\begin{tikzpicture}[xscale=.75, yscale=.5] \node at (0,0)[vx, scale=.75](0){}; \node at (1,.5)[vx, scale=.75](1){}; \node at (2,0)[vx, scale=.75](2){}; \node at (.5,1)[vx, scale=.75](3){}; \node at (1.5,1.5)[vx, scale=.75](4){}; \node at (2.5,1)[vx, scale=.75](5){}; \node at (0,2)[vx, scale=.75](6){}; \node at (1,2.5)[vx, scale=.75](7){}; \node at (2,2)[vx, scale=.75](8){}; \node at (3.25,1)[vx, scale=.75](9){}; \draw (0)--(1)--(2)--(0); \draw (3)--(4)--(5)--(3); \draw (6)--(7)--(8)--(6); \draw (0)--(3)--(6)--(0); \draw (1)--(4)--(7)--(1); \draw (2)--(5)--(8)--(2); \foreach \x in {2,5,8} {\draw (9)--(\x);} \draw (9) to [bend right=10](4); \draw (9) to [bend left =25](3); \end{tikzpicture} \\ \cline{2-2}\\[-2ex] %\cmidrule(lr){2-3} &\begin{tikzpicture}[xscale=.75, yscale=.5] \node at (0,0)[vx, scale=.75](0){}; \node at (1,.5)[vx, scale=.75](1){}; \node at (2,0)[vx, scale=.75](2){}; \node at (.5,1)[vx, scale=.75](3){}; \node at (1.5,1.5)[vx, scale=.75](4){}; \node at (2.5,1)[vx, scale=.75](5){}; \node at (0,2)[vx, scale=.75](6){}; \node at (1,2.5)[vx, scale=.75](7){}; \node at (2,2)[vx, scale=.75](8){}; \node at (3.25,1)[vx, scale=.75](9){}; \draw (0)--(1)--(2)--(0); \draw (3)--(4)--(5)--(3); \draw (6)--(7)--(8)--(6); \draw (0)--(3)--(6)--(0); \draw (1)--(4)--(7)--(1); \draw (2)--(5)--(8)--(2); \foreach \x in {2,5,8} {\draw (9)--(\x);} \draw (9) to [bend right=10](4); \draw (9) to [bend left=15](1); \draw (9) to [bend right=35](7); \end{tikzpicture} \\ \cline{2-2}\\[-2ex] &\begin{tikzpicture}[scale=.5] \foreach \x in {0,1,2,3,4} {\node at (360/5*\x:1cm)[vx, scale=.75](a\x){};} \foreach \x in {0,1,2,3,4} {\node at (360/5*\x+360/10:2cm)[vx, scale=.75](b\x){};} \draw (a0)--(b4)--(a4)--(b3)--(a3)--(b2)--(a2)--(b1)--(a1)--(b0)--(a0); %\draw (b0)--(b1)--(b2)--(b3)--(b4)--(b0); \draw (0,0) circle (2cm); %\draw (a0)--(a1)--(a2)--(a3)--(a4)--(a0); \draw (0,0) circle (1cm); \draw (a0)--(a2)--(a4)--(a1)--(a3)--(a0); \end{tikzpicture} \\ %\hline \end{tabular} \tabularnewline\hline \end{tabular} \caption{Values of $\indsat{n}{\claw}$ for $4\leq n\leq10$ along with trigraphs realizing those values. All $\claw$-induced-saturated graphs for $n=9$ and $n=10$ are shown.} \label{tab:claws} \end{table} In order to prove Theorem \ref{thm:claw-sis}, we first prove a series of lemmas. \begin{lem}\label{lem:sis_clawdeg}\label{deg2} Let $G$ be a \claw-induced-saturated graph. Then $G$ has \begin{enumerate} \item at most one isolated vertex, \item no vertices of degree one, \item at most one vertex of degree two, and \item at most two vertices of degree three. \end{enumerate} %Any graph $G$ that is \claw-induced-saturated (on $n\geq9$ vertices) does not have any vertices of degree one, has at most one isolated vertex, and has at most one vertex of degree two. Furthermore, if $G$ has an isolated vertex $v$, then $\delta(G-v)\geq4$. %If $G$ has an isolated vertex, then $G$ does not have any vertices of degree two or three \textcolor{green}{min deg of G-v is 4}; %otherwise $G$ has at most two vertices of degree three \textcolor{green}{flip}. \end{lem} \begin{proof} %$G$ cannot have two isolated vertices as adding an edge between them does not create a \claw. Let $G$ be a \claw-induced-saturated graph. Observe that if we had two isolated vertices, then adding the edge between them would not yield a $K_{1,3}$. Also, any edge of $G$ lies in a triangle, so there are no vertices of degree one. Suppose that $u$ and $v$ are vertices of degree two. Since every edge lies in a triangle the neighbors of $u$ are adjacent, as are the neighbors of $v$. Thus, if $u$ and $v$ are not adjacent, adding the edge $uv$ does not create an induced \claw. If $u$ and $v$ are adjacent, then $N[u] = N[v] = \{u,v,w\}$ for some $w$. However, removing $uw$ does not create an induced \claw as $v$ would have to have been its center. So $G$ has at most one vertex of degree two. To prove $(4),$ suppose $u$ is a vertex of degree three with neighbors $u_1,u_2,u_3$. Since every edge is in a triangle, we may assume that $u_1u_2, u_2u_3 \in E(G)$. \textit{Case 1:} $u_1u_3 \notin E(G)$. Then adding $u_1u_3$ creates an induced \claw centered at either $u_1$ or $u_3$; say $u_1$. Then $u_1$ has two nonadjacent neighbors $x$ and $y$ that are distinct from $u_2$ and $u_3$. However, $\{u,u_1,x,y\}$ induces a \claw in $G$, a contradiction. \textit{Case 2:} $u_1u_3 \in E(G)$. In particular, every vertex of degree three in $G$ is contained in a $K_4$. Let $v$ be another vertex of degree three. By the above, $N[v]$ induces $K_4$. If $uv \notin E(G)$, then adding $uv$ does not create an induced \claw. Thus, $u$ and $v$ are adjacent, and consequently the only vertices of degree three are contained in $N[u]$. If we remove $uu_1$, then an induced \claw exists, centered at either $u_2$ or $u_3$. So at least one of them has degree at least four, say $u_3$. Similarly, removing $uu_3$ creates an induced \claw centered at either $u_1$ or $u_2$ so that at least one of them has degree at least four. In any case, at most two vertices in $N[u]$, and as a result in $G$, have degree three. Thus, $(4)$ holds. If $G$ has an isolate, $u$, and another vertex $v$ with $\deg(v) \le 2$, then adding $uv$ cannot create an induced \claw unless $\deg(v) = 2$. In this case, the neighbors of $v$ cannot be adjacent, however every edge of $G$ must be in a triangle, a contradiction. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{lemma}\label{suff_claw} %Suppose $G$ is a graph such that every edge is in a triangle, the neighborhood of every vertex induces $2K_2$, and $G$ does not contain $K_4-e$\todo{Isn't this implied by the first assumption?}. If $G$ is a graph where the neighborhood of every vertex induces $2K_2$, then $G$ is \claw-induced-saturated. \end{lemma} \begin{proof} %Since $R(G)$=$V(G)$, then for any vertex $v\in V(G)$, $G[N(v)]\neq P_3$. %Thus $G$ does not contain $K_4-e$. Since no vertex has three independent neighbors, $G$ contains no induced \claw. Suppose we delete an edge $xy$. Since every edge is in a triangle, say $xyz$, deleting $xy$ leaves $z$ as the center of a \claw with leaves $x$, $y$, and any other neighbor of $z$. If we add an edge between two vertices with no common neighbors, then we take the new edge together with two nonadjacent neighbors of one of the vertices and find a \claw. Therefore it suffices to consider adding an edge $xy$, where $x$ and $y$ share a neighbor. Let $N(x)=\{u_1,u_2,v_1,v_2\}$ with $u_1u_2,v_1v_2 \in E(G)$, and suppose $u_1 \in N(y)$. Then $u_2 \notin N(y)$ otherwise $N(u_2)$ would contain a $P_3$ and not be $2K_2$. Similarly, both $v_1$ and $v_2$ cannot be in $N(y)$. So we may assume $v_2 \notin N(y)$. Then upon adding $xy$, $\{x,y,u_2,v_2\}$ induces a \claw. \end{proof} \begin{lemma} Let $G$ be a graph with at most one isolated vertex, where each nontrivial component is one of the graphs in Figure~\ref{fig:claw-i-s}. Then $G$ is \claw-induced-saturated. \end{lemma} \begin{figure} \centering \subcaptionbox{$H=K_3\cartprod K_3$, 9 vertices\label{k3xk3}}[.4\linewidth]{ \begin{tikzpicture}[xscale=2, yscale=1.5] \node at (0,0)[vx](0){}; \node at (1,.5)[vx](1){}; \node at (2,0)[vx](2){}; \node at (.5,1)[vx](3){}; \node at (1.5,1.5)[vx](4){}; \node at (2.5,1)[vx](5){}; \node at (0,2)[vx](6){}; \node at (1,2.5)[vx](7){}; \node at (2,2)[vx](8){}; \draw (0)--(1)--(2)--(0); \draw (3)--(4)--(5)--(3); \draw (6)--(7)--(8)--(6); \draw (0)--(3)--(6)--(0); \draw (1)--(4)--(7)--(1); \draw (2)--(5)--(8)--(2); \end{tikzpicture} }\hspace{1cm} \subcaptionbox{Graph $J$ on 11 vertices\label{11vtcs}}[.4\linewidth]{ %\includegraphics[scale=.5]{figures/claw_11} \begin{tikzpicture}[scale=.75] \draw (0,0) node[vx](b1) {}; \draw (2,0) node[vx](b2) {}; \draw (1,1) node[vx](b3) {}; \draw (b1)--(b2)--(b3)--(b1); \draw (-1,2) node[vx](r1) {}; \draw (3,2) node[vx](r2) {}; \draw (b1)--(r1)--(b3)--(r2)--(b2); \draw (1,3) node[vx](g1) {}; \draw (0,4) node[vx](g2) {}; \draw (2,4) node[vx](g3) {}; \draw (1,5) node[vx](g4) {}; \foreach \x in {1,...,4} {\foreach \y in {1,...,\x} \draw (g\x)--(g\y);} \draw (-1,6) node[vx](b4) {}; \draw (3,6) node[vx](b5) {}; \draw (g2)--(b4)--(g4)--(b5)--(g3); \draw (g2)--(r1)--(b4)--(b5)--(r2)--(g3); \draw (b1)--(g1)--(b2); \end{tikzpicture} } \subcaptionbox{Graph $K$ on 12 vertices\label{12vtcs}}[.4\linewidth]{ \begin{tikzpicture}[scale=0.25] \draw (0,0) circle (9cm); \foreach \x in {1,...,6} { \draw (150-60*\x:7cm) node[vx] (A\x) {}; } \foreach \x in {1,3,5} { \draw (120-60*\x:3cm) node[vx] (B\x) {}; } \foreach \x in {2,4,6} { \draw (120-60*\x:9cm) node[vx] (C\x) {}; \pgfmathparse{int(\x-1)} \draw (C\x) -- (A\x) -- (A\pgfmathresult); } \draw (A1) -- (C6); \draw (A3) -- (C2); \draw (A5) -- (C4); \foreach \x in {1,3,5} { \pgfmathparse{int(\x+1)} \draw (B\x) -- (A\x); \draw (A\pgfmathresult) -- (B\x); } \draw (B1) -- (B3) -- (B5) -- (B1); \draw (A1) -- (A6); \draw (A2) -- (A3); \draw (A4) -- (A5); \end{tikzpicture} } \subcaptionbox{Graph $L$ on 15 vertices\label{15vtcs}}[.4\linewidth]{ \begin{tikzpicture} \draw (0,0) circle (2.25cm); \foreach \x in {1,2,3,4,5}{\draw (360/5*\x:0.75cm) node[vx](a\x){};} \foreach \x in {1,2,3,4,5}{\draw (36+360/5*\x:1.5cm) node[vx](b\x){};} \draw (a1)--(a2)--(a3)--(a4)--(a5)--(a1); \foreach \x in {1,2,3,4,5}{\draw (360/5*\x:2.25cm) node[vx](c\x){};} \draw (a1)--(b1)--(a2)--(b2)--(a3)--(b3)--(a4)--(b4)--(a5)--(b5)--(a1); \draw (c1)--(b1)--(c2)--(b2)--(c3)--(b3)--(c4)--(b4)--(c5)--(b5)--(c1); \end{tikzpicture} } \caption{These graphs are \claw-induced-saturated.}\label{fig:claw-i-s} % For each graph $G$, white vertices belong to $R(G)$ and gray vertices belong to $B(G)$. \end{figure} \begin{proof} By inspection, the graph in Figure ~\ref{11vtcs} is \claw-induced-saturated, and since the graphs in Figures \ref{k3xk3}, \ref{12vtcs}, and \ref{15vtcs} have the property that the neighborhood of every vertex induces $2K_2$, they are \claw-induced-saturated by Lemma~\ref{suff_claw}. Now let $G$ be a graph with at most one isolated vertex and each of the remaining components are one of the graphs from Figure~\ref{fig:claw-i-s}. Since each nontrivial component of $G$ is \claw-induced-saturated, we only need to consider adding an edge $xy$ between components. When we add the edge $xy$, at least one of $x$ and $y$ must be in a nontrivial component, say $x$. By inspection we see every vertex in every graph of Figure \ref{fig:claw-i-s} has two nonadjacent neighbors, and in particular, this holds for $x$. Thus, $x$ together with these two neighbors and $y$ induce a \claw. Therefore, $G$ is \claw-induced-saturated. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We now can prove Theorem \ref{thm:claw-sis}. \begin{proof}[Proof of Theorem \ref{thm:claw-sis}] Lemma \ref{lem:sis_clawdeg} together with the degree-sum formula gives us the lower bound of $2n - 2$. To obtain the upper bound, we contruct graphs using $H, J, K$, and $L$ from Figure \ref{fig:claw-i-s}. These constructions will be based on the residue class of $n$ modulo 3. \begin{case}\label{0mod3} $n \equiv 0 \mod 3$, $n \geq 9$ \end{case} Use $\lfloor n/9 \rfloor-1$ copies of $H$, together with one copy of $H$, $K$, or $L$, for a graph with $2n$ edges. \begin{case} $n \equiv 1 \mod 3$, $n \geq 10$ \end{case} Use an isolated vertex with a graph from Case~\ref{0mod3} for a graph with $2n-2$ edges. \begin{case} $n \equiv 2 \mod 3$, $n\geq20$ or $n=11$. \end{case} If $n=11$, the graph $J$ suffices. If $n > 11$, then take $J$ and a construction from Case~\ref{0mod3}. This achieves $2n+2$ edges. \end{proof} It is worth noting that for $n \equiv 1 \mod 3$, $n \ge 10$, $\sis{n}{K_{1,3}} = 2n - 2$. Additionally, a detailed case analysis of degree sequences of $K_{1,3}$-induced-saturated graphs shows that $\sis{n}{K_{1,3}} \ge 2n$ for $n \not\equiv 1 \mod 3$. In particular, this implies $\sis{n}{K_{1,3}} = 2n$ for $n \equiv 0 \mod 3$, $n \ge 9$, and $2n \le \sis{n}{K_{1,3}} \le 2n + 2$ for $n \equiv 2 \mod 3$, $n \ge 20$. %end \claw subsubsection %%%%%%%%%%%%%%%%%%%%%%%%%% % % C4 AND MATCHINGS % %%%%%%%%%%%%%%%%%%%%%%%%%% \section{\texorpdfstring{$C_4$}~ and Matchings}\label{sec:small cycles} In this section we show that the induced saturation number of $C_4$ is zero for sufficiently large $n$, and we show that $(5/2)n \leq \sis{n}{C_4}\leq (7/64)n^2+o(n)$ % compute some bounds on $\sis{n}{C_4}$. Additionally, together with Observation \ref{thm:complement} and the fact that $\overline{C_4}=2K_2$, we use $C_4$-induced-saturated graphs to show that the induced saturation number of $kK_2$ is zero for $n$ sufficiently large and $k \ge 2$. We then show that $\sis{n}{kK_2}$ is constant in terms of $n$. %We begin with a general construction. \begin{cons}\label{gen gen icos} For $j \geq 5$ and $k \geq 2$, let $I_j^k$ be the following graph. Begin with $k$ copies of a wheel with $j$ spokes. Label the wheels $W^1,\ldots,W^k$, and label the vertices of $W^i$ so that its center is $w_0^i$, and the outer cycle of $W^i$ is $w_1^i,\ldots,w_j^i$. For each $i$ and $p$ with $1 \le i,p\le k$ and $i \neq p$, add the following edges: $w_\ell^i w_\ell^p$ for each $\ell \in [j]$; $w_\ell^i w_{\ell+1}^p$ for each $\ell \in [j-1]$; and $w_j^i w_1^p$. %For each $\ell \in [j]$ and $i \neq p$ (where $1 \le i,p \le k$), add the edges $w_\ell^i w_\ell^p$. For each $\ell \in [j-1]$ and $i \neq p$, add the edges $w_\ell^i w_{\ell+1}^p$. Finally, add the edges $w_j^i w_1^p$. %For $1\leq i p$, can be in our $C_4$, as either produces a triangle with $w_s^p$ and $w_{s+1}^p$. Now, $w_{s+1}^p$ must have another neighbor in our $C_4$. Suppose it is in $W^t$. If $t > p$, then it must be $w_{s+2}^t$ by the above. However, the only common neighbors $w_{s+2}^t$ and $w_s^p$ have are of the form $w_{s+1}^q$ where $q > p$, a contradiction. So $t < p$, and the other neighbor of $w_{s+1}^p$ is $w_{s+1}^t$. Again though, the only common neighbors of $w_s^p$ and $w_{s+1}^t$ are either of the form $w_{s+1}^q$ where $q > p$, or $w_s^r$ where $r < p$. In either case, we have a contradiction to the above. Thus, our $C_4$ has exactly one vertex from each wheel. Suppose our induced $C_4$ contains the vertices $w_{t_1}^p, w_{t_2}^q, w_{t_3}^r, w_{t_4}^s$. If $|\{t_1,t_2,t_3,t_4\}| \le 2$, then we have a triangle, a contradiction. If $|\{t_1,t_2,t_3,t_4\}| = 4$, then some vertex is not adjacent to two of the others, a contradiction. So $|\{t_1,t_2,t_3,t_4\}| = 3$, and two vertices have the same subscript. We may assume that it is $w_{t_1}^p, w_{t_2}^q = w_{t_1}^q$, and that $p < q$. Then, $w_{t_1}^p$ must have a neighbor not adjacent to $w_{t_1}^q$ in this $C_4$, say it is $w_{t_3}^r$. However, in order for this to be possible, we must have $t_3 = t_1 + 1$ and $p < r < q$. Thus, $w_{t_4}^s$ is adjacent to both $w_{t_1+1}^r$ and $w_{t_1}^q$. However, since $t_4$ must be distinct from both $t_1$ and $t_1 + 1$, this cannot happen, a contradiction. So $I_j^k$ is $C_4$-free. %By inspection \refedits{don't accept by inspection argument} we see that $I_j^k$ has the property that every edge is a diagonal of a $C_4$. Thus, removing any edge results in an induced $C_4$. So we only need to consider adding edges. We now must show that adding and removing edges from $I_j^k$ creates an induced $C_4$. We begin by considering removal of edges. The edges of $I_j^k$ can be classified into three types: edges that are on the outer cycle of a wheel, edges that are incident to the center of a wheel, and edges that are incident to two different wheels. If we remove an edge that is on the outer cycle of a wheel, , say $w_\ell^i w_{\ell+1}^i$ where $\ell \neq j$, then the vertices $w_0^i, w_\ell^i, w_{\ell+1}^i$, and $w_{\ell+1}^p$, where $p \neq i$, create an induced $C_4$. If $\ell = j$, then removing $w_j^i w_1^i$ creates a $C_4$ induced by the vertices $w_j^i, w_1^i, w_0^i$, and $w_1^p$, again where $p \neq i$. If we remove an edge that is incident to the center of a wheel, say $w_0^i w_\ell^i$, then $w_0^i, w_{\ell-1}^i, w_{\ell}^i$, and $w_{\ell+1}^i$ induce a $C_4$. Now, for $i \neq p$ and $\ell \in [j]$, we have the edge $w_\ell^i w_\ell^p$. Removing this edge creates a $C_4$ induced by the vertices $w_{\ell-1}^i, w_\ell^i, w_\ell^p$, and $w_{\ell+1}^p$, if $\ell \neq 1$, or by the vertices $w_j^i, w_1^i, w_1^p$, and $w_2^p$ if $\ell =1$. When $\ell \in [j-1]$, the edge $w_\ell^i w_{\ell+1}^p$ exists in $I_j^k$; removing it creates a $C_4$ induced by $w_\ell^i, w_\ell^p, w_{\ell+1}^p$, and $w_\ell^i$. Finally, removing the edge $w_j^i w_1^p$ from $I_j^k$ yields a $C_4$ induced by $w_j^i, w_j^p, w_1^p$, and $w_1^i$. To show that adding edges creates an induced $C_4$, we consider the different types of edges that are missing from $I_j^k$. Adding an edge within one wheel (say $W^m$) is simply adding a chord $w_i^m w_p^m$ to a 5-, 6-, or 7-cycle. If $p \neq i+2$ or $j = 5$, then this chord creates an induced 4-cycle. If $p = i+2$ and $j = 6$ or $j =7$, then if $m \neq k$, $w_i^m w_{i+1}^\ell w_{i+2}^\ell w_{i+2}^m w_i^m$ is an induced 4-cycle, where $\ell > m$, and if $m = k$, then $w_i^m w_{i+1}^m w_{i+1}^\ell w_i^\ell w_i^m$ is an induced $C_4$. Now suppose we add an edge between wheels, say $W^m$ and $W^\ell$, where we may assume $m < \ell$. If the new edge is between the centers of these wheels, that is, $w_0^m w_0^\ell$, then $w_0^m w_0^\ell w_1^\ell w_1^m w_0^m$ is an induced $C_4$. If it is from the center of $W_m$ to a vertex on the cycle of $W^\ell$, say $w_i^\ell$, then $w_0^m w_i^\ell w_{i+1}^\ell w_{i+1}^m w_0^m$ is an induced $C_4$; a similar cycle is also created if the new edge is $w_0^\ell w_i^m$. Finally, if we add an edge $w_i^m w_p^\ell$, note that $w_i^m$ is not adjacent to at least one of $w_p^m$ and $w_{p-1}^m$; label this vertex $u$. Since $u$ is adjacent to $w_{p}^\ell$, the vertices $w_0^m, w_i^m, w_p^\ell$, and $u$ induce a $C_4$. \end{proof} %} Proposition \ref{prop:C4indsat} implies that for many values of $n$, $\indsat{n}{C_4}=0$. In fact, this is the case for all $n \geq 12$. To show this, we use the following proposition regarding $kK_2$. While we only employ the proposition in the case $k = 2$, the more general statement which we present is not difficult. \begin{prop}\label{twins matching} Let $s:=(s_1,\dots, s_n)$ be a sequence of positive integers. Let $G$ be a graph with vertex set $\{v_1,\ldots v_n\}$, and let $G_s$ be the graph obtained from $G$ by replacing each vertex $v_i$ with an independent set of order $s_i$ and each edge with a complete bipartite graph between the corresponding independent sets. For $k \ge 2$, $G$ is $kK_2$-induced-saturated if and only if $G_s$ is $kK_2$-induced-saturated. \end{prop} Note that the graph $G_s$ constructed in this proposition is in fact the blow-up of $G$, as used in \cite{KSS}. %\refedits{Call it a blow-up, mention blow-up lemma} \begin{proof} For each vertex $v_i \in V(G)$, let $V_i$ be the independent set in $G_s$ that corresponds to it. We will call this collection of vertices in $G_s$ that replaces a single vertex in $G$ a \emph{part}. Note that %since no two vertices in a matching share the same neighborhood, no induced matching in $G_s$ uses two vertices from the same part, and the same holds if we add or remove a single edge from $G_s$. We claim that if $w_i$ and $w_j$ are vertices from different parts $V_i$ and $V_j$, respectively, of $G_s$, then $G_s$ (or $G_s+w_iw_j$ or $G_s-w_iw_j$) contains an induced matching %that uses no two vertices in the same part if and only if $G$ (resp. $G+v_iv_j$, or $G-v_iv_j$) contains an induced matching $M$. Suppose $M_s$ is such an induced matching in $G_s$ (or $G_s+w_iw_j$ or $G_s-w_iw_j$). Then each vertex in $M_s$ comes from a different part of $G_s$ (resp. $G_s+w_iw_j$ or $G_s-w_iw_j$), and thus they correspond to distinct vertices in $V(G)$. %each of which is only adjacent to the vertex corresponding to the one it was adjacent to in $M_s$. This is an induced matching in $G$. If $G$ (or $G+v_iv_j$ or $G-v_iv_j$) has an induced matching $M$, then when the graph is expanded, no new adjacencies have been added between the parts corresponding to the endpoints of vertices in $M$ (except for $w_iw_j$ in the case of $G+v_iv_j$). Thus, we can find an induced matching in $G_s$ (resp. $G_s+w_iw_j$ or $G_s-w_iw_j$). This shows that if $G_s$ is $kK_2$-induced-saturated, then so is $G$. To show that if $G$ is $kK_2$-induced-saturated, then so is $G_s$, it remains to consider adding edges between vertices in one part of $G_s$. First we note that $G$ has no dominating vertex. Indeed, if $u$ is a dominating vertex, then deleting an edge incident to $u$, say $uw$, does not create an induced $2K_2$, let alone an induced $kK_2$, as $u$ dominates $N_G(w)$. Now, suppose we add $w_iw_i'$ to $G_s$, in the part $V_i$ corresponding to $v_i$. Since $v_i$ is not dominating, there exists $w$ not adjacent to $v_i$. Since $G$ is $kK_2$-induced-saturated, $G+v_iw$ contains an induced matching $M=\{v_iw,x_2y_2,\ldots,x_ky_k\}$. Then\\ $M_s=\{w_iw_i',X_2Y_2,\ldots,X_kY_k\}$ is an induced matching in $G_s+w_iw_i'$, where $X_j$ and $Y_j$ are vertices in the parts corresponding to $x_j$ and $y_j$, respectively. \end{proof} %} \begin{cor} For $n \ge 12$, $\indsat{n}{C_4} = 0$. \end{cor} \begin{proof} Applying Observation \ref{thm:complement} to case $k = 2$ in Proposition \ref{twins matching}, allows us to begin with a graph that is $C_4$-induced-saturated, replace a single vertex with a clique of any order, replace the affected edges with complete bipartite graphs, and produce another graph that is $C_4$-induced-saturated. Thus, beginning with $I_5^2$, applying these operations obtains $C_4$-induced-saturated graphs for all values of $n \ge 12$. \end{proof} For $4 \le n \le 10$, a computer search showed $\indsat{n}{C_4} > 0$. At this time, the value of $\indsat{11}{C_4}$ is yet unknown. We now turn our attention to $\sis{n}{C_4}$. %Now that we have shown that $\indsat{n}{C_4}=0$ for $n \ge 12$, we turn our attention to computing $\sis{n}{C_4}$. \begin{thm}\label{prop:C4} For sufficiently large $n$, $(5/2)n \leq \sis{n}{C_4}\leq (7/64)n^2+o(n)$. \end{thm} \begin{proof} To prove the lower bound we show that $\delta(G) \ge 5$. Suppose $G$ is a $C_4$-induced-saturated graph. Let $x \in V(G)$, and let $H:=G[N(x)]$. Since deleting any edge produces an induced $C_4$, every edge is the diagonal of a $C_4$ and $\deg(x) \ge 3$. In particular, there exist $v_1,v_2,v_3 \in V(H)$ such that $v_1v_3$ is not an edge, but $v_1v_2$ and $v_2v_3$ are edges. Now, $G - xv_1$ contains an induced $C_4$ that contains both $x$ and $v_1$, but not $v_3$. If $v_2$ is not in this $C_4$, then there exist two other vertices distinct from $v_1,v_2,v_3$ in $H$. Thus, $\deg(x) \ge 5$. If $v_2$ is in this $C_4$, then there exists $v_4 \in V(H)$ distinct from $v_1,v_2,v_3$ such that $v_1v_4$ is an edge, but $v_2v_4$ is not. By a similar argument, considering $G - xv_3$ gives at least one additional vertex in $H$ distinct from $v_1,v_2,v_3,v_4$. So in any case, $\deg(x) \ge 5$, and as $x$ was arbitrary, $\delta(G) \ge 5$. Thus, provided $n \ge 12$, $\sis{n}{C_4} \ge (5/2)n$. %Starting with the icosahedron, applying Proposition~\ref{twins matching} and complementation yields a $C_4$-induced-saturated graph of order $n$, for any $n \ge 12$, that has minimum degree at least 5. Thus, $(5/2)n \leq \sis{n}{C_4}$ for every $n \ge 12$. %%%this was already mentioned in the discussion following 5.3 AND 5.2 To prove the upper bound, we choose $n \geq 56$ and create a graph $G$ of order $n$. Let $r \equiv n \mod 8$, where $0 \le r \le 7$. Set $k=\lfloor n/8 \rfloor$ so that $k \ge r$ and $v(I_7^k)=8k$. If $r=0$, choose $G=I_7^k$. If $r>0$, we create $G$ by adding $r$ vertices to $I_7^k$. Recall, as discussed after Proposition~\ref{twins matching}, by replacing the vertices of $I_7^k$ with cliques, and its edges with complete bipartite graphs, we preserve the property of being $C_4$-induced-saturated. Accordingly, using the notation of Construction~\ref{gen gen icos}, we replace $w_0^1,\ldots, w_0^r$ with copies of $K_2$ and make each new vertex adjacent to the neighborhood of the vertex it replaces. Now we determine $e(G)$. The first $r$ wheels have $22$ edges, and the rest have $14$. Between any two wheels there are $14$ edges. So $e(G)=14\left[\binom{k}{2}+k\right]+8r$. Since $r \in [0,7]$ and $k=\lfloor n/8 \rfloor$, $e(G) \leq \frac{7}{64}n^2+\frac{7}{8}n+56$. %Then each edge of $I_j^k$ is replaced by $\left(\displaystyle\frac{n}{(j+1)k}\right)^2$ edges, and each vertex of $I_j^k$ is a clique of order $\frac{n}{(j+1)k}$ in $G$. gives rise to approximately $\displaystyle\frac{1}{2}\left(\displaystyle\frac{n}{(j+1)k}\right)^2$ edges, so %\begin{align*} %e(G) \approx~&\|I_j^k\|\left(\frac{n}{(j+1)k}\right)^2+|I_7|\frac{1}{2}\left(\frac{n}{(j+1)k}\right)^2\\ % =~&jk(k+1)\left(\frac{n}{(j+1)k}\right)^2+(j+1)k\frac{1}{2}\left(\frac{n}{(j+1)k}\right)^2\\ % =~&n^2\left( \frac{j}{(j+1)^2}+\frac{3j+1}{2k(j+1)^2}\right). % \intertext{For fixed $j$, this quantity is minimized by taking $k$ as big as possible; that is, $k=n/(j+1)$, and (modulo a few stray vertices to make parity work out) $G=I_j^{n/(j+1)}$. Then,} % e(G)=~&\|I_j^{n/(j+1)}\| = j\left(\frac{n}{j+1}\right)\left(\frac{n}{j+1}+1\right)\\ % \approx~&j\left(\frac{n}{j+1}\right)^2. % \intertext{For $j=7$, this yields} % e(G)=~&\frac{7}{64}n^2 \approx 0.109n^2. % \end{align*} \end{proof} \subsection{Matchings} Another graph that is $C_4$-induced-saturated is the join $I_5^2 \vee K_{n-12}$. Observation \ref{thm:complement} implies that the complement of this graph is $2K_2$-induced-saturated. We can further generalize this to get a $kK_2$-induced-saturated graph for any $k\geq 2$. \begin{prop}\label{clm:match} Let $\overline{I_5^2}$ be the complement of the icosahedron. For fixed $k \ge 2$ and $n \geq 12(k-1)$, the graph $(k-1)\overline{I_5^2} + (n-12(k-1))K_1$ is $kK_2$-induced-saturated. Thus, for $n \geq 12(k-1)$, $\indsat{n}{kK_2}=0$. \end{prop} \begin{proof} By Proposition~\ref{prop:C4indsat} and Observation~\ref{thm:complement}, the complement of an icosahedron is $2K_2$-induced-saturated. Let $G$ denote $(k-1)\bar{I_5^2} + (n - 12(k - 1))K_1$. Clearly, $G$ contains $(k-1)K_2$ as an induced subgraph, but no induced $kK_2$. If we add or delete any edge inside a component, or add an edge among the isolates, we create an induced $kK_2$. Note that every vertex $v$ in $\bar{I_5^2}$ is in an induced copy of $K_2+K_1$ where $v$ is the isolate. Thus, adding any edge with an endpoint in a copy of $\bar{I_5^2}$ creates an induced $kK_2$. \end{proof} %} %An immediate corollary of Proposition \ref{clm:match} is an upper bound on $\sis{n}{kK_2}$ for any $n \ge 12(k-1)$. \begin{cor} For $n\geq 12(k-1)$, $\sis{n}{kK_2} \leq 36(k-1)$. \end{cor} In particular, for fixed $k$, $\sis{n}{kK_2}$ is constant. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ODD CYCLES ET AL % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Other Cycles and Generalizations of Cycles}\label{sec:weird cycles} In this section we provide a construction proving that odd cycles also have induced saturation number zero for $n$ sufficiently large. As it is already known that $\indsat{n}{C_3} = \sat{n}{C_3}$ \cite{MS}, we only consider odd cycles of length at least five. Additionally, this construction is also $H$-induced-saturated when $H$ is a modification of an even cycle as described below. Let $C_{2k}'$ denote a cycle of length $2k$ with a pendant vertex, and $\hat C_{2k}$ denote an even cycle with a chord between two vertices at distance 2 from each other (sometimes called a triangle chord or hop). For a given $k$ and $n \geq (k+1)^2+2$, we can write $n$ as $(k+1)t-s$ where $t$ and $s$ are integers with $t \geq k+2$ and $0 \leq s \leq t-3$. In particular, we choose $t=\cl{\frac{n}{k+1}}$. Using this expression for $n$, we give the following construction. \begin{cons}\label{cons:cycles} For $k \geq 3$ and $n \geq (k+1)^2+2$, let $n=(k+1)t-s$, where $t=\cl{\frac{n}{k+1}} \ge k+2$ and $0 \leq s \le t-3$. Let $G_{n,k}$ be formed from the Cartesian product $K_{k+1} \cartprod K_t$ by removing $s$ vertices from one copy of $K_t$. \end{cons} \begin{prop}\label{indsat_cycles} If $H \in \{C_{2k-1}, C_{2k}', \hat C_{2k}\}$, then the graph $G_{n,k}$ in Construction \ref{cons:cycles} is $H$-induced-saturated. \end{prop} \begin{proof} %NEW PROOF MAYBE BETTER? (NOW SLIGHTLY REVISED) Let $G_{n,k}$ be as described in Construction \ref{cons:cycles}. We first show that $G_{n,k}$ is $H$-free for $H \in \{C_{2k-1}, C_{2k}', \hat C_{2k}\}$. Any induced subgraph of $G_{n,k}$ that is triangle-free has at most two vertices from any copy of $K_{k+1}$ or $K_t$. Since $2k-1$ is odd, an induced $C_{2k-1}$ contains precisely one vertex $v$ from some copy of $K_{k+1}$. Then the neighbors of $v$ must be in the same copy of $K_t$, which means they form a triangle. Thus, $G_{n,k}$ has no induced odd cycle larger than a triangle. Since $\hat C_{2k}$ contains $C_{2k-1}$ as an induced subgraph, neither $C_{2k-1}$ nor $\hat C_{2k}$ are induced subgraphs of $G_{n,k}$. As $C_{2k}'$ contains $K_{1,3}$ as an induced subgraph, but $G_{n,k}$ does not, $G_{n,k}$ has no induced $C_{2k}'$. %Now notice that, given any vertex $u \in G_{n,k}$, $G[N(u)]=K_{t-1}+K_{k}$. So, no vertex in $G_{n,k}$ has three independent neighbors, hence $G_{n,k}$ has no induced $C'_{2k}$. % Similarly, if $G_{n,k}$ contained an induced $C'_{2k}$, then because $C'_{2k}$ is triangle-free with an odd number of vertices, then there exists one copy of $K_t$ that contains precisely one vertex $v$ of the subgraph. If $v$ is not the pendant vertex of $C_{2k}'$, it has at least two neighbors. However, these neighbors must be contained in the same copy of $K_{k+1}$ as $v$, forming a triangle in some copy of $K_{k+1}$. If $v$ is the pendant vertex, suppose it has neighbor $u$ on the cycle. Then $u$ has some neighbor $u'$ in a different copy of $K_t$ from itself, and $u,u'$, and $v$ are all in one copy of $K_{k+1}$, forming a triangle. Thus, $G_{n,k}$ has no induced $C'_{2k}$. In the remainder of this proof we view the vertices of $K_{k+1} \cartprod K_t$ as a $k+1$ by $t$ grid with vertices $v_{i,j}$ for $1 \le i \le k+1$ and $1 \le j \le t$. The vertices in each row induce $K_t$ and those in each column induce $K_{k+1}$. Note that $v_{i,j}$ is adjacent to $v_{m,p}$ if and only if $i=j$ or $m=p$. To create $G_{n,k}$ from this, we remove $s$ vertices from the last row of the grid. In particular, we remove $v_{k+1,t-s+1}, v_{k+1,t-s+2},\dots, v_{k+1,t}$. %Let $K_t^*$ denote the clique induced by the vertices in this last row. Thus, we can partition the vertices of $G_{n,k}$ into the following three sets: $R_1 = \{v_{i,j}: 1 \le i \le k, \, 1 \le j \le t - s\}$, $R_2 = \{v_{k+1,j}: 1 \le j \le t - s\}$, and $R_3 = \{v_{i,j}: 1 \le i \le k, \, t - s< j \le t\}$. Recall that $t - s \ge 3$, $t \ge k+2$, and $k \ge 3$. %Since $s \le t-3$ and $k \ge 3$, $G_{n,k}$ has at least three vertices in each row and column, and at least three rows with at least 4 vertices. In the following arguments, we will use the fact that as $t - s \ge 3$, $v_{1,1}, v_{1,2}, v_{1,3} \in R_1$ and $v_{k+1, 1}, v_{k+1,2}, v_{k+1,3} \in R_2$. Furthermore, we will use the path on $2k - 6$ vertices induced by the set $A = \{v_{p,p+1}, v_{p,p+2}: 2 \le p \le k - 2\}$. \begin{case} Adding edges \end{case} We first consider adding an edge to $G_{n,k}$. Observe that all the vertices in $R_1$ are interchangeable by switching rows and columns, and the same holds for the vertices in $R_2$ and $R_3$. So without loss of generality, there are five kinds of edges that can be added: an edge contained in $R_1$, contained in $R_3$, or between any two parts. Suppose we add an edge contained in $R_1$. Without loss of generality, assume it is $v_{1,1}v_{k,2}$. Let $B_1=\{v_{1,1}, v_{k,2}, v_{k+1,1}, v_{k+1,3}\}$. Then the vertex set $A \cup B_1 \cup \{v_{k,k}\}$ induces $C_{2k-1}$, the set $A \cup B_1 \cup \{v_{k,k}, v_{1,2}\}$ induces $\hat C_{2k}$, and the set $A \cup B_1 \cup \{v_{k-1,k}, v_{k-1, k+1}, v_{1,k+1}\}$ induces $C_{2k}'$ with pendant $v_{k,2}$. Suppose we add an edge contained in $R_3$. Without loss of generality, assume it is $v_{1,t}v_{k,t-1}$. Let $B_2=\{v_{1,t}, v_{k,t-1}, v_{k-1,k}, v_{k-1,t}\}$. Then the vertex set $A \cup B_2 \cup \{v_{k,3}\}$ induces $C_{2k-1}$, the set $A \cup B_2 \cup \{v_{k,2,}, v_{k,3}\}$ induces $\hat C_{2k}$, and the set $A \cup B_2 \cup \{v_{1,2}, v_{k+1,2}, v_{k+1,3}\}$ induces $C_{2k}'$ with pendant $v_{k,t-1}$. Suppose we add an edge between $R_1$ and $R_2$. Without loss of generality, assume it is $v_{1,1}v_{k+1,2}$. Let $B_3=\{v_{1,1}, v_{k+1,2}, v_{k-1,1}, v_{k-1,k}\}$. Then the vertex set $A \cup B_3 \cup \{v_{k+1,3}\}$ induces $C_{2k-1}$, the set $A \cup B_3 \cup \{v_{k+1,3}, v_{1,2}\}$ induces $\hat C_{2k}$, and the set $A \cup B_3 \cup \{v_{k,3}, v_{k,k+1}, v_{1,k+1}\}$ induces $C_{2k}'$ with pendant $v_{k+1,2}$. Suppose we add an edge between $R_1$ and $R_3$. Without loss of generality, assume it is $v_{1,1}v_{k,t}$. Let $B_4=\{v_{1,1}, v_{k,t}, v_{k+1,1}, v_{k+1,3}\}$. Then the vertex set $A \cup B_4 \cup \{v_{k,k}\}$ induces $C_{2k-1}$, the set $A \cup B_4 \cup \{v_{k,k}, v_{1,t}\}$ induces $\hat C_{2k}$, and the set $A \cup B_4 \cup \{v_{k-1,k}, v_{k-1,k+1}, v_{1,k+1}\}$ induces $C_{2k}'$ with pendant $v_{k,t}$. Suppose we add an edge between $R_2$ and $R_3$. Without loss of generality, assume it is $v_{1,t}v_{k+1,1}$. Let $B_5=\{v_{1,t}, v_{k+1,1}, v_{1,k}, v_{k,3}\}$. Then the vertex set $A \cup B_5 \cup \{v_{k,1}\}$ induces $C_{2k-1}$, the set $A \cup B_5 \cup \{v_{k,1}, v_{k,2}\}$ induces $\hat C_{2k}$, and the set $A \cup B_5 \cup \{v_{k,2}, v_{k-1,2}, v_{k-1,t}\}$ induces $C_{2k}'$ with pendant $v_{k+1,1}$. \begin{case} Deleting edges \end{case} There are several types of edges that we can delete within the categories of ``vertical'' and ``horizontal'' edges. There are three types of vertical edges: edges with both endpoints in $R_1$, both in $R_3$, and between $R_1$ and $R_2$. There are four types of horizontal edges: edges with both endpoints in $R_1$, both in $R_2$, both in $R_3$, and between $R_1$ and $R_3$. We first consider deleting vertical edges. Suppose we delete an edge contained in $R_1$ or an edge between $R_1$ and $R_2$. If the former, assume it is $v_{1,1}v_{k,1}$, and let $B_6 = \{v_{1,1},v_{k,1}, v_{k-1,3}, v_{1,k}\}$. If the latter, assume it is $v_{1,1}v_{k+1,1}$, and let\\ $B_6 = \{v_{1,1}, v_{k+1,1},v_{k-1,3}, v_{1,k}\}$. Then in either case, the vertex set $A \cup B_6 \cup \{v_{k-1,1}\}$ induces $C_{2k-1}$, and the set $A \cup B_6 \cup \{v_{k-1,1}, v_{k-1,2}\}$ induces $\hat C_{2k}$. If we deleted the edge $v_{1,1}v_{k,1}$, then set $A \cup B_6 \cup \{v_{k+1,1}, v_{k+1,2}, v_{k-1,2}\}$ induces $C_{2k}'$ with pendant $v_{k,1}$. If we deleted the edge $v_{1,1}v_{k+1,1}$, then the set $A \cup B_6 \cup \{v_{k,1}, v_{k,2}, v_{k-1,2}\}$ induces $C_{2k}'$ with pendant $v_{k+1,1}$. Suppose we delete an edge contained in $R_3$. Without loss of generality, assume it is $v_{1,t}v_{k,t}$. Let $B_7 = \{v_{1,t}, v_{k,t}, v_{1,k}, v_{k-1,t}\}$. Then the vertex set $A \cup B_7 \cup \{v_{k,3}\}$ induces $C_{2k-1}$, the set $A \cup B_7 \cup \{v_{k,2}, v_{k,3}\}$ induces $\hat C_{2k}$, and the set $A \cup B_7 \cup \{v_{k+1,2}, v_{k+1,3}, v_{k-1,2}\}$ induces $C_{2k}'$ with pendant $v_{k,t}$. We now consider deleting horizontal edges. Suppose we delete an edge contained in $R_1$ or contained in $R_2$. If the former, assume it is $v_{1,1}v_{1,3}$, and let $B_8 = \{v_{1,1}, v_{1,2},v_{1,3}, v_{k-1,k}\}$. If the latter, assume it is $v_{k+1,1}v_{k+1,3}$, and let $B_8 = \{v_{k+1,1}, v_{k+1,2}, v_{k+1,3},v_{k-1,k}\}$. Then in either case, the vertex set $A \cup B_8 \cup \{v_{k-1,1}\}$ induces $C_{2k-1}$, the set $A \cup B_8 \cup \{v_{k-1,1}, v_{k,1}\}$ induces $\hat C_{2k}$, and the set $A \cup B_8 \cup \{v_{k,2}, v_{k,k+1}, v_{k-1,k+1}\}$ induces $C_{2k}'$ with pendant $v_{1,1}$ when deleting $v_{1,1}v_{1,3}$, and pendant $v_{k+1,1}$ when deleting $v_{k+1,1}v_{k+1,3}$. Suppose we delete an edge between $R_1$ and $R_3$. Without loss of generality, assume it is $v_{1,3}v_{1,t}$. Let $B_9 = \{v_{1,3}, v_{1,t}, v_{1,1}, v_{k-1,k}\}$. Then the vertex set $A \cup B_9 \cup \{v_{k-1,t}\}$ induces $C_{2k-1}$, the set $A \cup B_9 \cup \{v_{k-1,t-1}, v_{k-1,t}\}$ induces $\hat C_{2k}$, and the set $A \cup B_9 \cup \{v_{k+1,1}, v_{k+1,2}, v_{k-1,2}\}$ induces $C_{2k}'$ with pendant $v_{1,t}$. Lastly, suppose we delete an edge contained in $R_3$. Without loss of generality, assume it is $v_{1,t-1}v_{1,t}$. Let $\tilde{A} = \{v_{p,t-k+p}, v_{p,t-k+p+1}: 2 \le p \le k - 2\}$, and let $\tilde{B} = \{v_{1,t-1}, v_{1,t}, v_{1,1}, v_{k-1,t-k+2}\}$. Since $t \ge k +2$, note that $t - k + 2 \ge 4$. Then the vertex set $\tilde{A} \cup \tilde{B} \cup \{v_{k-1,t}\}$ induces $C_{2k-1}$, the set $\tilde{A} \cup \tilde{B} \cup \{v_{k-1,t}, v_{k,t}\}$ induces $\hat C_{2k}$, and the set $\tilde{A} \cup \tilde{B} \cup \{v_{k+1,1}, v_{k+1,2}, v_{k-1,2}\}$ induces $C_{2k}'$ with pendant $v_{1,t}$. This completes the proof that $G_{n,k}$ is $H$-induced-saturated for $H \in \{C_{2k-1}, \hat{C_{2k}}, C_{2k}'\}$. \end{proof} %} \begin{cor}\label{cor:cycles} For all $k \geq 3$, if $n \geq (k+1)^2+2$ and $H\in\{C_{2k-1},C_{2k}',\hat C_{2k}\}$, then $\indsat nH =0$. \end{cor} In the following discussion assume $H \in \{C_{2k-1}, C_{2k}', \hat C_{2k}\}$. Using Construction \ref{cons:cycles} we obtain an upper bound on $\sis{n}{H}$ with order of magnitude $n^2$, which is trivial. We can improve this order of magnitude slightly in the case when $\lceil \sqrt{n}~ \rceil$ is not prime. To do so we note that if $n$ can be written as a product of two integers $s$ and $t$ that are both at least $k$, then the graph $K_s \cartprod K_t$ is $H$-induced-saturated. \begin{prop} Fix $k \ge 3$ and choose $n$ such that $n^{1/4} \ge k + 1$. \\ For $H \in \{C_{2k-1}, C_{2k}', \hat C_{2k}\}$, if $\lceil \sqrt{n}~ \rceil$ has a proper divisor $t \ge 3$, then $\sis{n}{H} \le cn^{7/4} + O(n^{3/2})$ for some constant $c$. \end{prop} \begin{proof} As noted above, the Cartesian product of two sufficiently large cliques is $H$-induced-saturated. So, consider $G := K_{\lceil \sqrt{n}~\rceil/t} \cartprod K_{t\lceil \sqrt{n}~ \rceil}$. Simple computation shows $n \le v(G) \le n + 2\sqrt{n} + 1$. So, $v(G)$ can be written as $n + s$, where $0 \le s \le 2\sqrt{n} + 1 \le t\sqrt{n} - 3$, as $t \ge 3$. Let $G'$ be obtained from $G$ by removing $s$ vertices from a single copy of $K_{3\lceil \sqrt{n}~\rceil}$ as in Construction \ref{cons:cycles}. An argument similar to that in Proposition \ref{indsat_cycles} shows that $G'$ is $H$-induced-saturated. Observe: $$e(G') \le t\lceil\sqrt{n}~\rceil \binom{(1/t)\lceil \sqrt{n}~\rceil}{2} + (1/t)\lceil\sqrt{n}~\rceil \binom{t\lceil \sqrt{n}~\rceil}{2} = \frac{\lceil \sqrt{n}~\rceil^2}{2}\left(\left(t+\frac{1}{t}\right)\lceil\sqrt{n}~\rceil) - 2\right).$$ Since $t$ divides $\lceil\sqrt{n}~\rceil$, $t \le \sqrt{\lceil \sqrt{n}~\rceil}\le c'n^{1/4}$ for some $c' > 1$. Using this and $\lceil\sqrt{n}~\rceil \le \sqrt{n} + 1$ gives $e(G') \le \frac{c'}{2}n^{7/4} + O(n^{3/2})$. \end{proof} Considering odd cycles points out another property of the induced saturation number. That is, if $\indsat{n}{H}=0$ for a particular $n$, it is not necessarily the case that $\indsat{k}{H}=0$ for all $k > n$. For example, Construction~\ref{cons:cycles} shows $\indsat{n}{C_5}=0$ for $n = 9$ and $n \geq 12$. However, a computer search showed that for $n=10$ and $n=11$, we have $\indsat{n}{C_5} > 0$. (A $C_5$-induced-saturated trigraph on 10 vertices with one gray edge is shown in Figure \ref{fig:C5_10}, so that $\indsat{10}{C_5}=1$.) %Thus, we have an example of a graph $H$ for which $\indsat{n}{H} =0$ but $\indsat{n+1}{H}\neq 0$. %\begin{prop} %For fixed $k \ge 3$ and $n \ge (k+1)^2+2$, $\frac{3}{2}n \le \sis{n}{H} \le n^{3/2}$, where $H \in \{C_{2k-1}, C_{2k}', %\hat{C_{2k}}\}$. %\end{prop} %%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[h] \centering \begin{tikzpicture}[scale=0.75] \foreach \y in {1,2,3} {\foreach \x in {1,2,3} {\draw (-3*\y,2*\y)+(90+120*\x:1cm) node[vx] (t\y\x){};} \draw (t\y1)--(t\y2)--(t\y3)--(t\y1);} \draw (t11)--(t21)--(t31); \draw (t31) to[out=-60, in=170] (t11); \draw (t13)--(t23)--(t33); \draw (t33) to[out=-15, in=120] (t13); \draw (t32)--(t22)--(t12); \draw (t32) to[out=-50, in=160] (t12); \draw (-4,8) node[vx, label=above:$v$] (v){}; \draw (t31)--(v)--(t33); \draw (t22)--(v)--(t12); \draw (t32) node[label= right:$v'$]{}; \draw [line width=3.6pt,dash pattern=on 1pt off 1pt] (t32) -- (v); \end{tikzpicture}%\includegraphics[scale=.4]{figures/c5_10} \caption{This trigraph, with the gray edge $vv'$, is a $C_5$-induced-saturated trigraph.} \label{fig:C5_10} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % FAMILIES OF GRAPHS % %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Families of Graphs}\label{sec:families} In this section we extend the definition of induced saturation to families of graphs in the natural way, and show the surprising result that a family $\mathcal F$ can consist entirely of graphs with induced-saturation number 0, yet satisfy $\indsat{n}{\mathcal F} > 0$. \begin{defn} For a family $\mathcal F$ of graphs, a trigraph $T$ is \textbf{$\mathcal F$-induced-saturated} if no realization of $T$ contains any member of $\mathcal F$ as an induced subgraph, but whenever any black or white edge of $T$ is turned to gray, some member of $\mathcal F$ occurs as an induced subgraph of some realization. The \textbf{induced saturation number} of $\mathcal F$ with respect to $n$, written $\indsat{n}{\mathcal F}$, is the minimum number of gray edges in an $\mathcal{F}$-induced-saturated trigraph with $n$ vertices. \end{defn} For any family $\mathcal F$ containing all graphs on $k$ vertices, $\indsat{n}{\mathcal F}=\binom{n}{2}$. Construction~\ref{cons:cycles} and Proposition~\ref{indsat_cycles} demonstrate that for any family $\mathcal F$, all of whose elements are odd cycles of length at least five, even cycles with a pendant, or even cycles with a triangle chord, $\indsat{n}{\mathcal F}=0$ for $n$ sufficiently large. However, we could have $\indsat{n}{\mathcal{F}}\neq 0$ even if there is some $G\in \mathcal{F}$ such that $\indsat{n}{G}=0$ %; for instance, any family containing $K_2$ trivially has induced saturation number zero. %Moreover, it is possible for a graph to have induced saturation number zero, but appear in a family with nonzero induced saturation number, as demonstrated in Proposition~\ref{threshold} below. One may suspect this is because of the presence of $P_4$, which has nonzero induced-saturation number, yet it is also possible for a family $\mathcal F$ to consist of graphs that each individually have induced saturation number zero, while the induced saturation number of $\mathcal F$ is nonzero. We provide an example of this in Proposition~\ref{split}. \begin{prop}\label{threshold} For all $n$, $\indsat{n}{\{2K_2,P_4,C_4\}} \neq 0$. \end{prop} \begin{proof} The graphs that contain no induced $2K_2,P_4,$ or $C_4$ are precisely the \emph{threshold graphs} \cite{CH}. These graphs are characterized in a second way: they are constructed by iteratively adding a vertex to a graph either as an isolate or a dominating vertex. Thus, an $n$-vertex threshold graph can be represented as a string of $n$ symbols from $\{-,+\}$ as follows: on the vertex set $V=\{v_1,\ldots,v_n\}$, for every $i>j$, $v_iv_j$ is an edge if and only if the $i$th symbol in the string is $+$. We claim that for any threshold graph $G$ with at least one edge, there exists $e \in E(G)$ such that $G-e$ is also threshold. Let $\pi=s_1, \ldots, s_n$ be a string of symbols from $\{-,+\}$ representing $G$. Suppose there exists $i \in [n-1]$ such that $s_i=-$ and $s_{i+1}=+$, and let $i$ be minimal with this property. Then the graph $G'=G-v_iv_{i+1}$ is represented by the symbol list $\pi'=s_1 \ldots s_{i-1}s_{i+1}s_is_{i+1}\ldots s_n$, so $G'$ is threshold. If no such index $i$ exists, then $\pi$ is a list consisting only of $+$, so $G$ is the complete graph $K_n$; however, $K_n-e$ is also threshold. Thus, for any graph $G$ with no induced $2K_2$, $P_4$, or $C_4$, there exists an edge $e \in G$ such that $G-e$ also has no induced $2K_2$, $P_4$, or $C_4$. It follows that $\indsat{n}{\{2K_2,P_4,C_4\}} \neq 0$. \end{proof} The family of {\it split graphs} is another family of graphs that can be characterized by a set of forbidden induced subgraphs. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. F\"oldes and Hammer~\cite{FH} showed that a graph is a split graph if and only if it contains no induced $2K_2$, $C_4$, or $C_5$. \begin{prop}\label{split} For all $n$, $\indsat{n}{\{2K_2,C_4,C_5\}} \neq 0$. \end{prop} \begin{proof} Since adding or deleting an edge between the clique part and the independent set of a split graph still results in a split graph, it follows that $\indsat{n}{\{2K_2, C_4, C_5\}} \neq 0$. \end{proof} We have shown that $\indsat{n}{2K_2}$, $\indsat{n}{C_4}$, and $\indsat{n}{C_5}$ are all equal to zero for sufficiently large $n$. Thus, this example shows that even though every graph in a family has induced-saturation number zero, the family itself may not have induced-saturation number zero. Other families characterized by a (not necessarily finite) family of forbidden induced subgraphs include %comparability graphs \cite{}, %too hard!!! perfect graphs \cite{CRST}, trivially perfect graphs \cite{W}, \cite{G}, interval graphs \cite{LB}, and line graphs \cite{B}. It would be interesting to determine $\indsat{n}{\mathcal F}$ and $\sis{n}{\mathcal F}$, if it exists, for these families. We suspect that doing so will be much more difficult than for threshold and split graphs, as the families of forbidden graphs are significantly more complicated. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} The authors would like to thank Michael Ferrara and Douglas West for their kind support and advice. We are also grateful to an anonymous reviewer for helpful suggestions that improved this paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{99} \bibitem{B} L.W.~Beineke. \newblock Characterizations of derived graphs. \newblock \emph{J. Combinatorial Theory} 9 (1970), 129-135 \bibitem{CRST} M.~Chudnovsky, N.~Robertson, P.~Seymour, R.~Thomas. \newblock The strong perfect graph theorem. \newblock \emph{Ann. of Math.} (2) 164 (2006), no. 1, 51-229. \bibitem{CS} M.~Chudnovsky, P.~Seymour.\newblock The structure of claw-free graphs. \newblock \emph{Surveys in Combinatorics} 2005, 153 - 171. \bibitem{CH} V.~Chv\'atal, P.L.~Hammer.\newblock Aggregation of inequalities in integer programming. \newblock \emph{Studies in integer programming (Proc. Workshop, Bonn, 1975)}, pp. 145-162. Ann. of Discrete Math., Vol. 1, North-Holland, Amsterdam, 1977. \bibitem{EHM} P.~Erd\H{o}s, A.~Hajnal, J.W.~Moon. \newblock A problem in graph theory. \newblock \emph{Amer. Math. Monthly} 71 (1964) 1107-1110. \bibitem{FFS} J.~Faudree, R.~Faudree, J.~Schmitt. \newblock A survey of minimum saturated graphs. \newblock {\it Electron. J. Combin.} (2011) Dynamic Survey 18. \bibitem{FH} S.~F\"oldes, P.L.~Hammer. \newblock On split graphs and some related questions. \newblock \emph{Probl\'emes Combinatoires et Th\'eorie Des Graphes,} 138-140, Orsay, France, 1976, Colloques internationaux C.N.R.S. 260 \bibitem{G} M.C.~Golumbic. \newblock Trivially perfect graphs. \newblock \emph{Discrete Math.} 24 (1978), no. 1, 105-107. \bibitem{KT} L.~Kaszonyi, Z.~Tuza Z. \newblock Saturated graphs with minimal number of edges. \emph{J. Graph Theory} 10 (1986), 203-210 \bibitem{KSS} J.~Koml\'os, G.N.~S\'ark\"ozy, E.~Szemer\'edi. \newblock Blow-up lemma. \emph{Combinatorica} 17 (1997), 109-127 \bibitem{LB} C.G.~Lekkerkerker, J.Ch.~Boland. \newblock Representation of a finite graph by a set of intervals on the real line. \newblock \emph{Fund. Math.} 51 1962/1963 45-64. \bibitem{MS} R. Martin, J.~Smith. \newblock Induced saturation number. \emph{Discrete Math.} 312 (2012), no. 21, 3096--3106. \bibitem{West} D.~West. \newblock {\it Introduction to Graph Theory}, 2nd. ed., Prentice Hall, Upper Saddle River, NJ, 2001. \bibitem{W} E.S.~Wolk. \newblock The comparability graph of a tree. \newblock \emph{Proc. Amer. Math. Soc.} 13 1962 789-795. \end{thebibliography} \end{document} %sagemathcloud={"zoom_width":125}