# Conjectures of TxGraffiti: Independence, domination, and matchings

1Yair Caro, 2Randy Davila, 3Michael A. Henning, and 2Ryan Pepper

1Department of Mathematics
University of Haifa–Oranim
Tivon 36006, Israel
e-mail<EMAIL_ADDRESS>

2Department of Mathematics and Statistics
University of Houston–Downtown
Houston, TX 77002, USA
e-mail<EMAIL_ADDRESS>
e-mail<EMAIL_ADDRESS>

3Department of Mathematics and Applied Mathematics
University of Johannesburg
Auckland Park, 2006 South Africa
e-mail<EMAIL_ADDRESS>

###### Abstract

TxGraffiti is an automated conjecturing program that produces graph theoretic
conjectures in the form of conjectured inequalities. This program written and
maintained by the second author since 2017 was inspired by the successes of
previous automated conjecturing programs including Fajtlowicz’s GRAFFITI and
DeLaViña’s GRAFFITI.pc. In this paper we prove and generalize several
conjectures generated by TxGraffiti when it was prompted to conjecture on the
_independence number_ , the _domination number_ , and the _matching number_
(and generalizations of each of these graph invariants). Moreover, in several
instances we also show the proposed inequalities relating these graph
invariants are sharp.

Keywords: Automated conjecturing; independence number; domination number;
matching number
AMS subject classification: 05C69

##  1 Introduction

Over the last decade there has been a surge in the use of artificial
intelligence and machine learning across a wide range of disciplines, with
many surprising breakthroughs. For example, machine learning clustering
algorithms provide effective web search and deep neural networks allow for
self-driving cars. Many of these modern advances in machine learning and
artificial intelligence are modeled on the basis of designing intelligent
machines to solve real world problems. Though applications of artificial
intelligence and machine learning are clearly important, it is worth noting
that the founder of artificial intelligence, Alan Turing, suggested in 1948
that designing machines to do mathematical research would be a good starting
point for this aim [43]. In considering Turing’s suggestion, two fundamental
questions arise: Can computers be designed to prove theorems? Can computers be
designed to pose meaningful conjectures? The latter of which we provide
evidence for in this paper.

The task of programming machines to form mathematical conjectures is referred
to as _automated conjecturing_ , and the first computer program to make
conjectures leading to published mathematical research was Fajtlowicz’s
GRAFFITI [21]. This program written in the early-1990’s, considers a small
collection of mathematical objects (predominantly simple graphs) and invokes
heuristics, that by design limit both the number of output statements of the
program and the quality of output statements of the program. One notable
result inspired by a conjecture of GRAFFITI and related to graph theory is the
result due to Favaron, Mahéo, and Saclé [25], which states that $\alpha(G)\geq
R(G)$, where $\alpha(G)$ is the _independence number_ of the graph $G$ and
$R(G)$ is the _residue_ of the graph $G$.

As a successor to GRAFFITI, DeLaViña’s GRAFFITI.pc [20] also invokes
heuristics on a collection of graphs in order to produce graph theoretic
conjectures. Unlike GRAFFITI, GRAFFITI.pc maintains and computes data on
millions of graphs and has been particularly successful in generating
conjectures related to domination type graph invariants. GRAFFITI and
GRAFFITI.pc are not the only notable automated conjecturing programs, and we
would like to mention Lenat’s AM [33, 34, 35], Epstein’s GT [22, 23], Colton’s
HR [15, 16, 17], Hansen and Caporossi’s AGX [7, 8, 4], and Mélot’s Graphedron
[37].

In this paper we consider conjectures of the automated conjecturing program
_TxGraffiti_. This program written in the Python programming language
(versions 3.6 and higher) by the second author in 2017, and subsequence
versions written in 2019 and 2020, produces conjectures on simple connected
graphs. Currently, TxGraffiti stores all connected graphs on 8 or less
vertices, all connected cubic graphs on up to 16 vertices, and several other
graphs that appear in the literature. For each graph that is stored in the
programs database, TxGraffiti also stores pre-computed numerical and boolean
values stored for the graph in question. For example, a graph’s order, size,
domination number, and independence number are stored, together with
properties of the graph such as claw-free, triangle-free, or planar; among
many other numerical invariants and structural properties. For a video demo of
using TxGraffiti, see [18].

The conjectures produced by TxGraffiti are in the form of proposed
inequalities relating graph invariants subject to some structural property. We
note that TxGraffiti has already produced conjectures that have led to
publishable mathematical results, for example, one conjecture of TxGraffiti
inspired the surprising result given in [13], which states
$\delta(G)\alpha(G)\leq\Delta(G)\mu(G)$ for graphs with minimum degree
$\delta(G)$, maximum degree $\Delta(G)$, and _matching number_ $\mu(G)$. For a
notable open conjecture of TxGraffiti, we mention the conjecture which states
$Z(G)\leq\alpha(G)+1$, where $G\neq K_{4}$ is a connected cubic graph and
$Z(G)$ is the _zero forcing number_ of $G$; a partial solution to this
conjecture is given in [19].

In the following sections of this paper we present, generalize, and prove
conjectures of TxGraffiti when the program was asked to focus on the
independence number, the edge domination number, and the connected domination
number. In doing so, we give further evidence for the usefulness of TxGraffiti
and other automated conjecturing programs in stimulating mathematical
research.

Graph Terminology and Notation. Throughout this paper all graphs will be
considered undirected, simple, and finite. We in general follow the graph
theory notation and terminology in [32]. In particular, the order of a graph
$G$ with vertex set $V(G)$ and edge set $E(G)$ is $n(G)=|V(G)|$, whereas the
size of $G$ is $m(G)=|E(G)|$. Two vertices $v,w\in V(G)$ are neighbors, or
adjacent, if $vw\in E(G)$. The open neighborhood of $v\in V(G)$, is the set of
neighbors of $v$, denoted $N_{G}(v)$, whereas the closed neighborhood is
$N_{G}[v]=N_{G}(v)\cup\\{v\\}$. The open neighborhood of $S\subseteq V$ is the
set of all neighbors of vertices in $S$, denoted $N_{G}(S)$, whereas the
closed neighborhood of $S$ is $N_{G}[S]=N_{G}(S)\cup S$. The degree of a
vertex $v\in V$ is denoted by $d_{G}(v)=|N_{G}(v)|$. The maximum and minimum
degree of $G$ is denoted by $\Delta(G)$ and $\delta(G)$, respectively. For
$r\geq 1$ an integer, an $r$-_regular graph_ is a graph with all vertices of
degree $r$.

For a set of vertices $S\subseteq V(G)$, the subgraph induced by $S$ is
denoted by $G[S]$. If $v\in V(G)$, we denote by $G-v$ the graph obtained from
$G$ by deleting $v$. We denote the path, cycle, and complete graph on $n$
vertices by $P_{n}$, $C_{n}$, and $K_{n}$, respectively. A _triangle_ in $G$
is a subgraph of $G$ isomorphic to $K_{3}$, whereas a _diamond_ in $G$ is a
subgraph of $G$ isomorphic to $K_{4}$ with one edge removed. A graph $G$ is
_$F$ -free_ if $G$ does not contain $F$ as an induced subgraph. In particular,
if $G$ is $F$-free, where $F=K_{1,3}$, then $G$ is _claw-free_. Claw-free
graphs are heavily studied and an excellent survey of claw-free graphs has
been written by Flandrin, Faudree, and Ryjacek [26].

Two edges in a graph $G$ are _independent_ if they are not adjacent in $G$;
that is, if they have no vertex in common. For a set $M$ of edges of $G$, we
let $V(M)$ denote the set of vertices of $G$ that are incident with an edge in
$M$. The set $M$ is a _matching_ in $G$ if the edges in $M$ are pairwise
disjoint, that is, $|V(M)|=2|M|$. A matching of maximum cardinality is a
_maximum matching_ , and the cardinality of a maximum matching of $G$ is the
_matching number_ of $G$, denote by $\mu(G)$. If $M$ is a matching of $G$, a
vertex is _$M$ -matched_ if it is incident with an edge of $M$; otherwise, the
vertex is _$M$ -unmatched_.

A matching $M$ in $G$ is _maximal_ if it is maximal with respect to inclusion,
that is, the set $V(G)\setminus V(M)$ is independent. The minimum cardinality
of a maximal matching in $G$ is the _edge domination number_ of $G$, denoted
by $\gamma_{e}(G)$. A maximal matching in $G$ of cardinality $\gamma_{e}(G)$
is a _minimum maximal matching_. Matchings in graphs are extensively studied
in the literature (see, for example the classic book on matching by Lovász and
Plummer [36], and the excellent survey articles by Plummer [39] and
Pulleyblank [41]). Edge domination in graphs is well studied with over 125
papers listed on MathSciNet to date. For a recent paper, we refer the reader
to [6].

The _independence number_ , $\alpha(G)$, of $G$ is the maximum cardinality of
an independent set of vertices in $G$. For $k\geq 0$ an integer, a set
$S\subseteq V(G)$ is a $k$-_independent set_ in $G$ if $\Delta(G[S])\leq k$.
The cardinality of a maximum $k$-independent set in $G$ is the
$k$-_independence number_ of $G$, denoted by $\alpha_{k}(G)$. We note that the
$0$-independence number of $G$ is the classic independence number, that is,
$\alpha(G)=\alpha_{0}(G)$. The independence and $k$-independence numbers are
very well-studied in the literature, and a survey article is given by
Chellali, Favaron, Hansberg, and Volkmann [14]. A refer to [1, 3, 9, 10, 12,
24, 31] for a few selected papers on $k$-independence.

A set $S$ of vertices in a graph $G$ is a _dominating set_ if every vertex not
in $S$ is adjacent to a vertex in $S$. A dominating set $S$ with the
additional property that every vertex in $S$ is adjacent to some other vertex
in $S$ is a _total dominating set_ , abbreviated TD-set of $G$. Moreover, a
dominating set that is independent is an _independent dominating set_. A
dominating set $S$ of $G$ such that $G[S]$ is connected is a _connected
dominating set_. For $k\geq 1$, a $k$-_dominating set_ of $G$ is a dominating
set $S$ such that every vertex outside $S$ has at least $k$ neighbors in $S$,
that is, $|N_{G}(v)\cap S|\geq k$ for every vertex $v\in V(G)\setminus S$. The
_domination number_ $\gamma(G)$ of $G$ is the minimum cardinality of a
dominating set of $G$, and a dominating set of $G$ of cardinality $\gamma(G)$
is called a $\gamma$-_set of $G$_. The _total domination number_ ,
_independent domination number_ , _connected domination number_ , _$k$
-domination number_ are defined analogously, and denoted by $\gamma_{t}(G)$,
$i(G)$, $\gamma_{c}(G)$ and $\gamma_{k}(G)$, respectively. For recent books on
domination and total domination in graphs, we refer the reader to [29, 30,
32].

For sets $X$ and $Y$ of vertices in a graph $G$, we denote by $[X,Y]$ the set
of edges of $G$ with one end in $X$ and the other end in $Y$. For $\ell\geq 1$
an integer, we use the standard notation $[\ell]=\\{1,\ldots,\ell\\}$.

##  2 Independence versus domination

In this section we prove and generalize several conjectures of TxGraffiti
relating independence and domination in graphs. For similar results relating
these two invariants, see also [11, 28, 38]. The first TxGraffiti conjecture
we consider relates the independence number to the total domination number.

######  Conjecture 1 (TxGraffiti, confirmed.)

If $G$ is a connected cubic graph, then
$\alpha(G)\leq\frac{3}{2}\gamma_{t}(G)$.

As with many conjectures of TxGraffiti, natural generalizations can be found
with some inspection. This is the case for Conjecture 1, and we will prove
this generalization. However, before providing this result, we first define a
class of graphs that were discovered while considering its statement. For
$r\geq 2$, let $\mathcal{G}_{r}$ be the family of all $r$-regular bipartite
graphs $G$ for which there exists a partition $V(G)=A\cup B$, where $A$
induces an $(r-1)$-regular graph and $B$ induces a $1$-regular graph.

For example, the graph $G$ shown in Figure 1(a) is a $3$-regular graph that
belongs to the family $\mathcal{G}_{3}$, and the graph $G$ shown in Figure
1(b) is a $4$-regular graph that belongs to the family $\mathcal{G}_{4}$.
Further, we note that the graph $G$ in Figure 1(a) satisfies
$\alpha(G)=\frac{3}{2}\gamma_{t}(G)$, while the graph $G$ shown in Figure 1(b)
satisfies $\alpha(G)=\frac{4}{2}\gamma_{t}(G)=\frac{1}{2}\gamma_{t}(G)$.

(a)(b) Figure 1: Graphs in the families $\mathcal{G}_{3}$ and
$\mathcal{G}_{4}$

Suppose that $G\in\mathcal{G}_{r}$ for some $r\geq 2$. Thus, $G$ is a
$r$-regular bipartite graph that contains a partition $V(G)=A\cup B$, where
$A$ induces an $(r-1)$-regular subgraph and $B$ induces a $1$-regular graph.
Let $G$ have order $n$, and so $n=|A|+|B|$. Since every vertex in $A\cup B$
has a neighbor in $B$, the set $B$ is a TD-set of $G$, and so
$\gamma_{t}(G)\leq|B|$. Doubling counting edges between $A$ and $B$, we have
$(r-1)|B|=|A|=n-|B|$, and so $\gamma_{t}(G)\leq|B|=n/r$. Every graph $G$ of
order $n$ without isolated vertices satisfies $\gamma_{t}(G)\geq n/\Delta(G)$.
In our case the graph $G$ is $r$-regular, and so $\gamma_{t}(G)\geq n/r$.
Consequently, $\gamma_{t}(G)=n/r$. By definition the graph
$G\in\mathcal{G}_{r}$ is a regular bipartite graph, implying that
$\alpha(G)=n/2$. As observed earlier, $\gamma_{t}(G)=n/r$. Consequently,
$\alpha(G)=\frac{r}{2}\gamma_{t}(G)$. We state this formally as follows.

###### Observation 2

For $r\geq 2$, if $G\in\mathcal{G}_{r}$, then
$\alpha(G)=\frac{r}{2}\gamma_{t}(G)$.

For $r\geq 2$, the independence number and total domination number of an
$r$-regular graph are related as follows.

###### Theorem 3

For $r\geq 2$, if $G$ is an $r$-regular graph, then

$\alpha(G)\leq\frac{r}{2}\gamma_{t}(G),$

with equality if and only if $G\in\mathcal{G}_{r}$.

Proof. For $r\geq 2$, let $G$ be an $r$-regular graph of order $n$. Let $D$ be
a $\gamma_{t}$-set of $G$, and so $D$ is a TD-set of $G$ and
$|D|=\gamma_{t}(G)$. Further, let $Q=V(G)\setminus D$. Since $D$ is a TD-set
of $G$, each vertex in $D$ is adjacent with at most $r-1$ vertices in $Q$.
Furthermore since $D$ is a dominating set, every vertex in $Q$ has at least
one neighbor in $D$. Thus, the number of edges between $D$ and $Q$ is at most
$(r-1)|D|$ and at least $|Q|=n-|D|$, from which we deduce;

$\gamma_{t}(G)=|D|\geq\frac{n}{r}.$ (1)

As first observed in 1964 by Rosenfeld [42], the independence number of a
regular graph is at most one-half its order, that is,
$\alpha(G)\leq\frac{1}{2}n$. Hence, by Equation (1), we have

$\gamma_{t}(G)\geq\frac{n}{r}\geq\frac{2}{r}\alpha(G),$ (2)

or, equivalently, $\alpha(G)\leq\frac{r}{2}\gamma_{t}(G)$. This establishes
the desired upper bound in the statement of the theorem.

Suppose, next, that $G$ is an $r$-regular graph that satisfies
$\alpha(G)=\frac{r}{2}\gamma_{t}(G)$ where $r\geq 2$. This implies that the
inequalities in Inequality Chains (1) and (2) are all equalities. Therefore,
$\gamma_{t}(G)=|D|=\frac{n}{r}$ and $\alpha(G)=\frac{1}{2}n$. Moreover, every
vertex in $D$ is adjacent with exactly $r-1$ vertices in $Q$, and every vertex
in $Q$ has exactly one neighbor in $D$ (for otherwise, we would have strict
inequality in Inequality (1)). Hence, the subgraph $G[Q]$ of $G$ induced by
the set $Q$ is an $(r-1)$-regular graph, and the subgraph $G[D]$ of $G$
induced by the set $D$ is a $1$-regular graph. Therefore, $|D|=n/r$ and
$|Q|=n(r-1)/r$. Since $\alpha(G)=\frac{1}{2}n$, the graph $G$ is a bipartite
graph. Hence, $G$ is an $r$-regular bipartite graph for which there exists a
partition $V(G)=A\cup B$, where $A=Q$ induces an $(r-1)$-regular graph and
$B=D$ induces a $1$-regular graph. Therefore by definition, we have
$G\in\mathcal{G}_{r}$. Conversely, if $G\in\mathcal{G}_{r}$, then by
Observation 2, we have $\alpha(G)=\frac{r}{2}\gamma_{t}(G)$. $\Box$

TxGraffiti also produces conjectures on graphs with forbidden subgraphs. We
remark that if a TxGraffiti presents to the user a conjecture that requires a
forbidden subgraph, then the proposed inequality must be false for at least
one graph with the forbidden subgraph present. That is, TxGraffiti will only
produce an inequality relating graph invariants for the largest possible
family of graphs for which the inequality is true. For example, the following
conjecture states that the independence number of connected and claw-free
graphs is bounded from above by the $2$-domination number, and so, among all
connected graphs, TxGraffiti found at least one graph with $K_{1,3}$ as an
induced subgraph which does not satisfy this relationship.

######  Conjecture 4 (TxGraffiti, confirmed.)

If $G$ is a connected claw-free graph, then $\alpha(G)\leq\gamma_{2}(G)$.

As with Conjecture 1, a natural generalization of Conjecture 4 was not
difficult to deduce from the original proposed inequality, and we prove this
generalization with the following theorem.

###### Theorem 5

For $r\geq 3$ and $k\geq 0$, if $G$ is a $K_{1,r}$-free graph and
$j=r(k+1)-1$, then

$\alpha_{k}(G)\leq\gamma_{j}(G),$

and this bound is sharp.

Proof. For integers $r\geq 3$ and $k\geq 0$, let $G$ be a $K_{1,r}$-free graph
and let $j=r(k+1)-1$. Let $I$ be a maximum $k$-independent set of $G$, and let
$D$ be a minimum $j$-dominating set of $G$. That is, $|I|=\alpha_{k}(G)$ and
$|D|=\gamma_{j}(G)$. Next let $A=I\setminus D$ and $B=D\setminus I$. We note
that $I=A\cup(I\cap D)$ and $D=B\cup(I\cap D)$. If $A=\emptyset$, then
$I\subseteq D$, and so $\alpha_{k}(G)=|I|\leq|D|=\gamma_{j}(G)$. Hence, we may
assume $A\neq\emptyset$, for otherwise the desired result, namely
$\alpha_{k}(G)\leq\gamma_{j}(G)$, is immediate.

Suppose that $B=\emptyset$. If $D\subset I$ and $v$ is an arbitrary vertex in
$I\setminus D$, then $v$ has at least $j$ neighbors in $D$. However since
$j=r(k-1)-1>k$, this would imply that $v$ has strictly greater than $k$
neighbors in $D$, contradicting the fact that $I$ is a $k$-independent set of
$G$. Hence, in this case when $B=\emptyset$, we must have $D=I$, and so
$\alpha_{k}(G)=|I|=|D|=\gamma_{j}(G)$. Hence, we may further assume
$B\neq\emptyset$, for otherwise the desired result is immediate.

Recall that $D=B\cup(I\cap D)$ and that $A=I\setminus D$. Since $I$ is a
$k$-independent set of $G$, every vertex in $A$ is adjacent to at most $k$
vertices in $I\cap D$. Since $D$ is a $j$-dominating set of $G$, every vertex
in $A$ is adjacent to at least $j=r(k+1)-1$ vertices in $D$, implying that
every vertex in $A$ is adjacent to at least $r(k+1)-1-k=(r-1)(k+1)$ vertices
in $B$. Thus, the number of edges, $|[A,B]|$, between $A$ and $B$ is given by

$|[A,B]|\geq(r-1)(k+1)|A|.$ (3)

Suppose that some vertex $v\in B$ has at least $(r-1)(k+1)+1$ neighbors in
$A$. Let $A_{v}=N(v)\cap A$, and let $G_{v}=G[A_{v}]$ be the subgraph of $G$
induced by the set $A_{v}$. Thus, $G_{v}$ has order $|A_{v}|\geq(r-1)(k+1)+1$.
We note that the maximum degree $\Delta(G_{v})$ in $G_{v}$ is at most $k$.
Therefore,

$\alpha(G_{v})\geq\frac{|V(G_{v})|}{\Delta(G_{v})+1}\geq\frac{(r-1)(k+1)+1}{k+1}>r-1,\vspace{0.1cm}$

implying that $\alpha(G_{v})\geq r$. Let $I_{v}$ be a maximum independent set
in $G_{v}$, and so $|I_{v}|=\alpha(G_{v})\geq r$. We note that the graph
$G[I_{v}\cup\\{v\\}]=K_{1,r}$, contradicting our supposition that the graph
$G$ is $K_{1,r}$-free. Hence, every vertex in $B$ has at most $(r-1)(k+1)$
neighbors in $A$, implying that

$|[A,B]|\leq(r-1)(k+1)|B|.$ (4)

By Inequalities (3) and (4), we have $|A|\leq|B|$. Thus,

$\alpha_{k}(G)=|I|=|A|+|I\cap D|\leq|B|+|I\cap D|=|D|=\gamma_{j}(G).$

This completes the proof of Theorem 5.

To see this bound is sharp, consider the family of graphs constructed after
the proceeding corollary, one of which is illustrated in Figure 2. $\Box$

As a special case of Theorem 5, when $r=3$ and $k=0$, we confirm Conjecture 4
in the affirmative. This result is stated formally with the following
corollary, where we further establish sharpness with the infinite family of
graphs proceeding its statement.

###### Corollary 6

If $G$ is a connected claw-free graph, then

$\alpha(G)\leq\gamma_{2}(G),$

and this bound is sharp.

To see that the bound in Corollary 6 is sharp, let $\ell\geq 1$ and let
$G_{\ell}$ be the graph constructed as follows. Take $\ell$ vertex disjoint
copies of $P_{2}$, say $P^{1}_{2},\dots,P^{\ell}_{2}$, and $\ell+1$ isolated
vertices, say $v_{1},v_{2},\dots,v_{\ell+1}$, and join both vertices of
$P^{i}_{2}$ to the two vertices $v_{i}$ and $v_{i+1}$ for all $i\in[\ell]$.
The resulting graph $G_{\ell}$ is a claw-free graph. The set
$\\{v_{1},v_{2},\dots,v_{\ell+1}\\}$ is both a maximum independent set in
$G_{\ell}$ and a $2$-dominating set of $G_{\ell}$. Therefore, by Corollary 6,
we have $\ell+1\leq\alpha(G_{\ell})\leq\gamma_{2}(G_{\ell})\leq\ell+1$. Hence,
we have equality throughout this inequality chain, implying that
$\alpha(G_{\ell})=\gamma_{2}(G_{\ell})$. See Figure 2 for one such example.

Figure 2: A claw-free graph $G$ with $\alpha(G)=\gamma_{2}(G)$.

For $k\geq 0$, the _local $k$-independence number_ $\alpha_{k,L}(G)$ of a
graph $G$ is the maximum $k$-independence number among all subgraphs of $G$
induced by the open neighborhoods of the vertices, that is,

$\alpha_{k,L}(G)=\max_{v\in V(G)}\left\\{\alpha_{k}(G[N(v)])\right\\}.$

A second generalization of Conjecture 4, using a similar proof strategy, and
involving local $k$-independence number is presented below. Conjecture 4 is
the special case of the theorem below when $r=3$ and $k=0$.

###### Theorem 7

For $k\geq 0$ and $r\geq k+2$, if $G$ is a connected graph with
$\alpha_{k,L}(G)\leq r-1$, then

$\alpha_{k}(G)\leq\gamma_{r+k-1}(G).$

Proof. For integers $k\geq 0$ and $r\geq k+2$, let $G$ be a connected graph
with $\alpha_{k,L}(G)\leq r-1$. Let $I$ be a maximum $k$-independent set of
$G$, and let $D$ be a minimum $(r+k-1)$-dominating set of $G$. That is,
$|I|=\alpha_{k}(G)$ and $|D|=\gamma_{r+k-1}(G)$. Let $A=I\setminus D$ and
$B=D\setminus I$. If $A=\emptyset$, then $I\subseteq D$, and so
$\alpha_{k}(G)=|I|\leq|D|=\gamma_{r+k-1}(G)$. Hence, we may assume that
$A\neq\emptyset$. Suppose that $B=\emptyset$. If $D\subset I$ and $v$ is an
arbitrary vertex in $I\setminus D$, then $v$ has at least $r+k-1\geq k+1$
neighbors in $D$, contradicting the fact that $I$ is a $k$-independent set of
$G$. Hence, $D=I$, and so $\alpha_{k}(G)=|I|=|D|=\gamma_{r+k-1}(G)$. Hence, we
may further assume $B\neq\emptyset$, for otherwise the desired result is
immediate.

Since $I$ is a $k$-independent set of $G$, every vertex in $A$ is adjacent to
at most $k$ vertices in $I\cap D$. Since $D$ is a $(r+k-1)$-dominating set of
$G$, every vertex in $A$ is therefore adjacent to at least $r-1$ vertices in
$B$, and so

$|[A,B]|\geq(r-1)|A|.$ (5)

Suppose that some vertex $v\in B$ has at least $r$ neighbors in $A$. Since the
local $k$-independence number of $G$ is at most $r-1$, this implies that the
set of neighbors of $v$ in $A$ induces a subgraph of $G$ with maximum degree
strictly greater than $k$. However, such a subgraph of $G$ is a subgraph of
the graph $G[I]$ which has maximum degree at most $k$, a contradiction. Hence,
every vertex in $B$ has at most $(r-1)$ neighbors in $A$, implying that

$|[A,B]|\leq(r-1)|B|.$ (6)

By Inequalities (5) and (6), we have $|A|\leq|B|$. Thus,

$\alpha_{k}(G)=|I|=|A|+|I\cap D|\leq|B|+|I\cap D|=|D|=\gamma_{r+k-1}(G).$

This completes the proof of Theorem 7. $\Box$

While both Theorems 5 and 7 are generalizations of Conjecture 4, and happen to
coincide in the case that $k=0$, they become different for higher values of
$k$. In general, Theorem 7 has a better bound on $\alpha_{k}(G)$ than Theorem
5, at the cost of a stronger hypothesis. This means that by excluding more
subgraphs than just $K_{1,r}$, Theorem 7 yields a better upper bound than
Theorem 5. For example, when $k=3$ and $r=5$, Theorem 5 gives the result that
$\alpha_{3}(G)\leq\gamma_{19}(G)$, provided $G$ is $K_{1,5}$-free. In the same
conditions on $k$ and $r$, Theorem 7 gives the result that
$\alpha_{3}(G)\leq\gamma_{7}(G)$, provided $G$ has maximum local
$3$-independence number of at most 4 (which means that $G$ is $K_{1,5}$-free,
in addition to having many other forbidden subgraphs).

##  3 Edge domination versus matching

In this section we prove and generalize a conjecture of TxGraffiti on the edge
domination number of a graph. Recall that the edge domination number
$\gamma_{e}(G)$ of a graph $G$ is the minimum cardinality of maximal matching
in $G$, and a minimum maximal matching is a maximal matching in $G$ of
cardinality $\gamma_{e}(G)$. The following conjecture of TxGraffiti inspired
this sections main result.

######  Conjecture 8 (TxGraffiti, confirmed.)

If $G$ is a connected cubic graph, then $\gamma_{e}(G)\geq\frac{3}{5}\mu(G)$.

While investigating the bound posed in Conjecture 8, we subsequently
established a more general and stronger lower bound on the edge domination
number in terms of the order, maximum degree, and minimum degree. This result
is given formally by the following theorem.

###### Theorem 9

If $G$ is a graph of order $n$, minimum degree $\delta\geq 1$, and maximum
degree $\Delta$, then

$\gamma_{e}(G)\geq\frac{\delta n}{2(\Delta+\delta-1)}.$

Proof. Let $G$ be a graph a graph of order $n$, minimum degree $\delta\geq 1$,
maximum degree $\Delta$, and let $M$ be a minimum maximal matching in $G$. Let
$A$ be the set of $M$-matched vertices, and so, $A=V(M)$ and
$|A|=2|M|=2\gamma_{e}(G)$. Let $B=V(G)\setminus A$, and so
$|B|=n-2\gamma_{e}(G)$. By the maximality of the matching $M$, the set $B$ is
an independent set. By double counting the number of edges, $|[A,B]|$, between
$A$ and $B$ we have

$\delta(n-2\gamma_{e}(G))=\delta|B|\leq|[A,B]|\leq(\Delta-1)|A|=2(\Delta-1)\gamma_{e}(G),$

or, equivalently, $\gamma_{e}(G)\geq\delta n/(2(\Delta+\delta-1))$. $\Box$

If $G$ is a graph of order $n$, then $\mu(G)\leq\frac{1}{2}n$. A _perfect
matching_ is a matching that matches every vertex; that is, if a graph $G$ of
order $n$ has a perfect matching, then $n$ is even and $\mu(G)=\frac{1}{2}n$.
As an immediate consequence of Theorem 9 we have the following results.

###### Corollary 10

If $G$ is a graph of order $n$, minimum degree $\delta\geq 1$, and maximum
degree $\Delta$, then

$\gamma_{e}(G)\geq\left(\frac{\delta}{\Delta+\delta-1}\right)\mu(G).$

###### Corollary 11

For $r\geq 1$, if $G$ is an $r$-regular graph, then
$\gamma_{e}(G)\geq\left(\frac{r}{2r-1}\right)\mu(G)$.

In the special case when $r=3$ in the statement of Corollary 11 we have the
following result, which resolves Conjecture 8 in the affirmative.

###### Corollary 12

If $G$ is a connected cubic graph, then $\gamma_{e}(G)\geq\frac{3}{5}\mu(G)$.

##  4 Connected domination versus matching and independence

Next we investigate the connected domination number. Our main results
concerning connected domination were inspired by the following two TxGraffiti
conjectures, both of which we resolve in the affirmative as corollaries to
more general results we present in this section.

######  Conjecture 13 (TxGraffiti, confirmed.)

If $G$ is a connected cubic graph, then $\gamma_{c}(G)\geq\mu(G)-1$.

######  Conjecture 14 (TxGraffiti, confirmed.)

If $G$ is a connected cubic graph, then $\gamma_{c}(G)\geq\alpha(G)-1$.

Conjecture 14 inspired the following more general theorem focusing on the
connected domination number. We remark that the following result first
appeared in [2] as a consequence of an upper bound on the _zero forcing
number_ of a graph. The proof we provide is different in that our proof
technique is focused only on the connected domination number. Moreover, as a
consequence of our proceeding arguments we are also able to establish a
characterization of equality in the following bound.

###### Theorem 15

For $r\geq 2$, if $G$ is a connected $r$-regular graph of order $n$, then

$\gamma_{c}(G)\geq\frac{n-2}{r-1}.$

Proof. For $r\geq 2$, let $G$ be a connected $r$-regular graph with order $n$.
If $G$ contains a dominating vertex, then $G=K_{r+1}$. In this case, $n=r+1$
and $\gamma_{c}(G)=1=\frac{n-2}{r-1}$. Hence, we may assume that $G$ does not
contain a dominating vertex, and so, $\gamma_{c}(G)\geq 2$. Let $D$ be a
$\gamma_{c}$-set of $G$, and so $D$ is a connected dominating set of $G$ such
that $|D|=\gamma_{c}(G)\geq 2$. Since the subgraph $G[D]$ induced by $D$ is
connected, it contains a spanning tree $T$ of size $|D|-1$. Let
$A=V(G)\setminus D$. Each vertex in $A$ has at least one neighbor in $D$. Thus
by double counting the number of edges, $|[A,D]|$, between $A$ and $D$, we
have by the $r$-regularity of $G$ that

$\begin{array}[]{lcl}n-|D|=|A|&\leq&|[A,D]|\vspace{0.1cm}\\\
&=&\displaystyle{\sum_{v\in D}d_{G}(v)-2|E(G[D])|\vspace{0.1cm}}\\\
&\leq&r|D|-2|E(T)|\vspace{0.1cm}\\\
&=&r|D|-2(|D|-1),\vspace{0.1cm}\end{array}$

or, equivalently, $(r-1)|D|\geq n-2$, and so
$\gamma_{c}(G)=|D|\geq\frac{n-2}{r-1}$. $\Box$

For $r\geq 3$, we define a tree $T$ to be a $(1,r)$-tree if every vertex of
$T$ has degree $1$ or $r$. Let $L(T)$ denote the set of all leaves in a tree
$T$, and let $\ell(T)=|L(T)|$, and so $\ell(T)$ is the number of leaves in the
tree $T$. We proceed further with the following lemma. Again, we need remark
that the following result first appeared in [2] as a consequence of an upper
bound on the _zero forcing number_ of a graph. However, and as before, our
proof technique presented here is solely focused on the maximum number of
leaves and excludes any notion of zero forcing in graphs.

###### Lemma 16

For $r\geq 3$, if $T$ is a tree of order $n$ and maximum degree $\Delta(T)\leq
r$, then

$\ell(T)\leq\frac{(r-2)n+2}{r-1},$

with equality if and only if $T$ is a $(1,r)$-tree.

Proof. For $r\geq 3$, let $T$ be a tree of order $n$, size $m$ and maximum
degree $\Delta(T)\leq r$. Let $n_{i}$ denote the number of vertices of degree
$i$ in $T$ for $i\in[r]$. Thus,

$\sum_{i=1}^{r}n_{i}=n\hskip 14.22636pt\mbox{and}\hskip
14.22636pt\sum_{i=1}^{r}i\cdot n_{i}=2m=2(n-1),$ (7)

and so

$\sum_{i=2}^{r}(i-1)n_{i}=n-2.$

Hence,

$(r-1)n_{r}=n-2-\sum_{i=2}^{r-1}(i-1)n_{i}\leq n-2,$

and so,

$n_{r}\leq\frac{n-2}{r-1}.$ (8)

By (7), we have

$\sum_{i=1}^{r}(i-(r-1))n_{i}=2(n-1)-(r-1)n,$

or, equivalently,

$\sum_{i=1}^{r}(r-i-1)n_{i}=(r-3)n+2.$ (9)

By Inequality (8) and Equation (9), we have

$\begin{split}(r-2)n_{1}&=(r-3)n+2+n_{r}+\sum_{i=2}^{r-1}(i+1-r)n_{i}\\\
&\leq(r-3)n+2+\frac{n-2}{r-1}+\sum_{i=2}^{r-1}(i+1-r)n_{i}\\\
&\leq\frac{(r-2)^{2}\cdot n+2(r-2)}{r-1},\end{split}$

noting that $(i+1-r)n_{i}\leq 0$ for all $i\in\\{2,\dots,r-1\\}$. Thus,

$\ell(T)=n_{1}\leq\frac{(r-2)n+2}{r-1}.$ (10)

Further, if we have equality in Inequality (10), then we must have equality
throughout the above inequality chains, implying that $n_{i}=0$ for
$i\in\\{2,\dots,r-1\\}$. Hence, if we have equality in Inequality (8), then
$T$ is a $(1,r)$-tree.

Conversely, if $T$ is a $(1,r)$-tree, then $n_{1}+n_{r}=n$ and $n_{1}+r\cdot
n_{r}=2m=2n-2$, and so

$n_{r}=\frac{n-2}{r-1},$

which implies that

$\ell(T)=n_{1}=\frac{(r-2)n+2}{r-1}.$

This completes the proof of the lemma. $\Box$

As a consequence of Lemma 16, we have the following result.

###### Theorem 17

For $r\geq 3$ if $G$ is a connected graph of order $n$ and maximum degree
$\Delta(G)\leq r$, then

$\gamma_{c}(G)\geq\frac{n-2}{r-1},$

with equality if and only if $G$ has a spanning $(1,r)$-tree.

Proof. For $r\geq 3$, let $G$ be a connected graph of order $n$ and maximum
degree $\Delta(G)\leq r$. We note that $\gamma_{c}(G)=n-\ell(T)$, where $T$ is
a spanning tree of $G$ with the maximum number of leaves. Since $\Delta(G)\leq
r$, we note that $\Delta(T)\leq r$. Thus, by Lemma 16, we have

$\gamma_{c}(G)=n-\ell(T)\geq n-\frac{(r-2)n+2}{r-1}=\frac{n-2}{r-1},$

with equality if and only if $T$ is a spanning $(1,r)$-tree in $G$. $\Box$

We remark that recognizing if $G$ has $(1,r)$-spanning tree is NP-Complete for
$r=2$, since this amounts to Hamiltonian path problem as can be seen in [40].
On the other hand, it is easy to construct such regular graphs with spanning
$(1,r)$-tree. To see this construction, begin with any $(1,r)$-tree $T$,
having $n$ vertices and $n_{1}=\frac{n(r-2)+2}{(r-1)}$ are leaves. Next take
any $(r-1)$-regular graph $G$ on $n_{1}$ vertices, which may not necessarily
connected, and embed $G$ in the set formed by the leaves of $T$ to obtain the
desired $r$-regular graph with a spanning $(1,r)$-tree.

As observed in [42], if $G$ is a regular graph of order $n$ without isolated
vertices, then $\alpha(G)\leq\frac{1}{2}n$. As observed earlier, if $G$ is a
graph of order $n$, then $\mu(G)\leq\frac{1}{2}n$. Hence as a consequence of
Theorem 17, we have a lower bound on the connected domination number of a
connected regular graph in terms of the matching number and regularity.
Furthermore, Caro et al. [13] recently proved $\mu(G)\geq\alpha(G)$ for all
$r$-regular graphs with $r\geq 2$. Thus, we have the following result.

###### Corollary 18

For $r\geq 2$, if $G$ is a connected $r$-regular graph, then

$\gamma_{c}(G)\geq\frac{2\mu(G)-2}{r-1}\geq\frac{2\alpha(G)-2}{r-1}.$

In the special case of Corollary 18 when $r=3$, we have that if $G$ is a
connected cubic graph, then $\gamma_{c}(G)\geq\mu(G)-1$ and
$\gamma_{c}(G)\geq\alpha(G)-1$. This proves Conjectures 13 and 14. We state
this result formally as follows.

###### Corollary 19

If $G$ is a connected cubic graph, then the following holds.
(a) $\gamma_{c}(G)\geq\mu(G)-1$.
(b) $\gamma_{c}(G)\geq\alpha(G)-1$.

## References

  * [1] A. Abiad, G. Coutinho, and M. A. Fiol, On the $k$-independence number of graphs. Discrete Math. 342 (2019), 2875–2885.
  * [2] D. Amos, Y. Caro, R. Davila, and R. Pepper, Upper bounds on the $k$-forcing number of a graph, Discrete Appl. Math. 181 (2015), 1–10.
  * [3] D. Amos, R. Davila, and R. Pepper, On the $k$-residue of disjoint unions of graphs with applications to $k$-independence, _Discrete Mathematics_ 321 (2014), 24-34.
  * [4] M. Aouchiche, G. Caporossi, P. Hansen and M. Laffay, Autographix: a survey, _Electron. Notes Discrete Math._ , 22 (2005), 515–520.
  * [5] A. Babikir and M. A. Henning, Domination versus independent domination in graphs of small regularity. Discrete Math. 343 (2020), no. 7, 111727, 9 pp.
  * [6] J. Baste, M. Fürst, M. A. Henning, E. Mohr, and D. Rautenbach, Domination versus edge domination. Discrete Appl. Math. 285 (2020), 343–349.
  * [7] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs: 1 the autographix system, _Discrete Math._ , 212 1 (2000), 29–44.
  * [8] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures, _Discrete Math._ , 276 1 (2004), 81–94.
  * [9] Y. Caro and A. Hansberg, New approach to the $k$-independence number of a graph. Electron. J. Combin. 20 (2013), no. 1, Paper 33, 17 pp.
  * [10] Y. Caro. New results on the independence number. _Tech. Report_ , Tel-Aviv University, 1979.
  * [11] Y. Caro and R. Pepper, Degree sequence index strategy, _Australasian Journal of Combinatorics_ , Vol. 59(1) (2014), Pages 1-23.
  * [12] Y. Caro and Z. Tuza. Improved lower bounds on $k$-independence. J. Graph Theory 15 (1991), no. 1, 99–107.
  * [13] Y. Caro, R. Davila, and R. Pepper. New results relating independence and matchings. Discuss. Math. Graph Theory, in press (2021). DOI: https://doi.org/10.7151/dmgt.2317
  * [14] M. Chellali, O. Favaron, A. Hansberg, and L. Volkmann, $k$-domination and $k$-independence in graphs: a survey. Graphs Combin. 28 (2012) no. 1, 1–55.
  * [15] S. Colton, A. Bundy and T. Walsh, Automated concept formation in pure mathematics, _Proceedings of the 16th International Joint Conference on Artificial Intelligence,_ vol. 2, IJCAI’99, Morgan Kaufmann Publishers (1999), 786–791.
  * [16] S. Colton, Refactorable numbers–a machine invention, _J. Integer Seq._ , 2 (99.1) (1999), p. 2.
  * [17] S. Colton, Automated Theory Formation in Pure Mathematics, Springer, Heidelberg (2002).
  * [18] R. Davila, TxGraffiti Demo, https://www.youtube.com/watch?v=B8b3Kl9f9IA (2021).
  * [19] R. Davila and M.A. Henning, Zero forcing in claw-free cubic graphs, _Bulletin of the Malaysian Mathematical Sciences Society_ , Volume 43 (2020), 673–688.
  * [20] E. DeLaVina, Graffiti.pc: a variant of Graffiti, _DIMACS Ser. Discret. Math. Theor. Comput. Sci._ , 69 (2005), p. 71.
  * [21] E. DeLaVina, Some history of the development of Graffiti, _Graphs and Discovery, DIMACS Ser. Discret. Math. Theor. Comput. Sci._ , vol. 69, Amer. Math. Soc., Providence, RI (2005), 81–118.
  * [22] S.L. Epstein, On the discovery of mathematical theorems, _IJCAI_ (1987), 194–197.
  * [23] S.L. Epstein, Learning and discovery: one system’s search for mathematical knowledge, _Comput. Intell._ , 4 (1) (1988), pp. 42-53
  * [24] S. Fajtlowicz, Independence, clique size and maximum degree. Combinatorica 4 (1984), 35–38.
  * [25] O. Favaron, M. Mahéo, and J. F. Saclé, On the residue of a graph. J. Graph Theory 15 (1991), 39–64.
  * [26] E. Flandrin, R. Faudree, and Z. Ryjacek, Claw-free graphs – a survey. Discrete Math. 214, (2016), 196–200.
  * [27] W. Goddard, M. A. Henning, J. Lyle, and J. Southey, On the independent domination number of regular graphs. Annals Combin. 16 (2012), 719–732.
  * [28] A. Hansberg and R. Pepper, On $k$-domination and $j$-independence in graphs, _Discrete Applied Mathematics_ 161 (2013), 1472-1480.
  * [29] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning (eds), Topics in Domination in Graphs. Developments in Mathematics, vol 64. Springer, Cham. (2020) DOI 10.1007/978-3-030-51117-3.
  * [30] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning (eds), Structures of Domination in Graphs. Developments in Mathematics, vol 66. Springer, Cham. (2021) DOI 10.1007/978-3-030-58892-2
  * [31] M. A. Henning, C. Löwenstein, J. Southey, and A. Yeo, A new lower bound on the independence number of a graph and applications. Electron. J. Combin. 21 (2014), no. 1, Paper 1.38, 12 pp.
  * [32] M. A. Henning and A. Yeo, _Total domination in graphs (Springer Monographs in Mathematics)_ 2013\. ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online).
  * [33] D.B. Lenat, The ubiquity of discovery, _Artif. Intell._ , 9 3 (1977), 257–285.
  * [34] D.B. Lenat, On automated scientific theory formation: a case study using the am program, _Mach. Intell._ , 9 (1979), 251–286.
  * [35] D.B. Lenat, The nature of heuristics, _Artif. Intell._ , 19 2 (1982), 189–249.
  * [36] L. Lovász and M. D. Plummer, _Matching Theory_ , North-Holland Mathematics Studies, vol. 121, Ann. Discrete Math., vol. 29, North-Holland, 1986.
  * [37] H. Mélot, Facet defining inequalities among graph invariants: the system graphedron, _Discrete Appl. Math._ , 156 10 (2008), 1875–1891.
  * [38] R. Pepper, Implications of some observations about the $k$-domination number, _Congr. Numer._ 206 (2010), 65-71.
  * [39] M. Plummer, Factors and Factorization. 403–430. _Handbook of Graph Theory_ _ed._ J. L. Gross and J. Yellen. CRC Press, 2003, ISBN: 1-58488-092-2.
  * [40] C. Picouleau, Complexity of the hamiltonian cycle in regular graph problem, _Theoretical Computer Science_ , 131 (1994), 463–473.
  * [41] W. R. Pulleyblank, Matchings and Extension. 179–232. _Handbook of Combinatorics_ _ed._ R. L. Graham, M. Grötschel, L. Lovász. Elsevier Science B.V. 1995, ISBN 0-444-82346-8.
  * [42] M. Rosenfeld, Independent sets in regular graphs. Israel J. Math. 2 (1964), 262–272.
  * [43] A. Turing, Intelligent machinery, _The Essential Turing_ , (2004), 395–432.