# Minimal prime graphs of finite solvable groups

Chris Florez, Jonathan Higgins, Kyle Huang, Thomas Michael Keller, Dawei Shen
Chris Florez, Department of Mathematics, David Rittenhouse Lab, University of
Pennsylvania, 209 South 33rd Street, Philadelphia, PA 19104-6395, USA
<EMAIL_ADDRESS>Jonathan Higgins, Mathematics and Computer Science
Department, Wheaton College, 501 College Ave, Wheaton, IL 60187, USA
<EMAIL_ADDRESS>Kyle Huang, Mathematics Department, University
of California-Berkeley, 2227 Piedmont Avenue, Berkeley, CA 94720, USA
<EMAIL_ADDRESS>Thomas M. Keller, Department of Mathematics, Texas
State University, 601 University Drive, San Marcos, TX 78666-4616, USA
<EMAIL_ADDRESS>Dawei Shen, Department of Mathematics and Statistics,
Washington University in St. Louis, 1 Brookings Dr., St. Louis, MO 63105, USA
<EMAIL_ADDRESS>
###### Abstract.

We explore graph theoretical properties of minimal prime graphs of finite
solvable groups. In finite group theory studying the prime graph of a group
has been an important topic for the past almost half century. Recently prime
graphs of solvable groups have been characterized in graph theoretical terms
only. This now allows the study of these graphs with methods from graph theory
only. Minimal prime graphs turn out to be of particular interest, and in this
paper we pursue this further by exploring, among other things, diameters,
Hamiltonian cycles and the property of being self-complementary for minimal
prime graphs. We also study a new, but closely related notion of minimality
for prime graphs and look into counting minimal prime graphs.

###### Key words and phrases:

Prime graph, Solvable group, $3$-colorable, triangle-free

###### 2010 Mathematics Subject Classification:

Primary: 20D10, Secondary: 05C25

##  1\. Introduction

The topic of this paper are prime graphs of finite solvable groups. The prime
graph of a finite group is the graph whose vertices are the prime numbers
dividing the order of the group, with two vertices being linked by an edge if
and only if their product divides the order of some element of the group.
Prime graphs were introduced by Gruenberg and Kegel in the 1970s and have been
an object of continuous study since then. They were among the first graphs
assigned to groups. This idea of representing group theoretical data via
graphs and describing them via graph theoretical notions proved so successful
that today there is a myriad of graphs (e.g. character degree graphs,
conjugacy class size graphs, etc.) and a whole industry of exploring them. For
this reason, today prime graphs are often referred to as Gruenberg-Kegel
graphs.

While a focus in the study of prime graphs has been on simple groups for a
long time, the main result of [8], somewhat surprisingly, is a purely graph
theoretical characterization of prime graphs of solvable groups: A (simple)
graph is the prime graph of a finite solvable group if and only if its
complement is triangle-free and 3-colorable. This made it possible to study
simple groups whose prime graph is that of a finite solvable group, see [6].
Moreover, this characterization allowed the authors of [8], for solvable
groups, to introduce and study the idea of minimal prime graphs: connected
graphs whose complement is triangle-free and 3-colorable, but removing an edge
means that the complement has a triangle or is no longer 3-colorable. As
outlined in detail in [8], the groups whose prime graphs are minimal are
groups which are "saturated in Frobenius actions" and have a restricted, but
highly non-trivial structure.

In this paper we will turn our focus to graph theoretical properties of
minimal prime graphs. Some important properties of minimal prime graphs were
already proved in [8], such as having complement with chromatic number 3 and
having an induced 5-cycle. We add to this by exploring diameters, Hamiltonian
cycles, the property of being self-complementary, and others. We also take a
look at counting minimal prime graphs. Moreover, we introduce an alternative
notion of minimal prime graphs - minimally connected prime graphs - which
turns out to be closely related to minimal prime graphs.

##  2\. Minimally Connected Prime Graphs and Minimal Prime Graphs

Below, we provide a formal definition for the Minimally Connected Prime Graphs
that we will be studying throughout this paper.

######  Definition.

A minimally connected prime graph (MCPG) is a graph $\Gamma$ with at least two
vertices such that

  1. (1)

$\Gamma$ is connected

  2. (2)

$\overline{\Gamma}$ is triangle-free

  3. (3)

$\overline{\Gamma}$ is 3-colorable

  4. (4)

The removing of any edge results in a violation of at least one of the
conditions (i), (ii), or (iii).

Of particular interest are what we refer to as complete bridge graphs.

######  Definition.

A complete bridge graph, denoted $B_{m,n}$, is a graph on $m+n$ points, where
$m$ of the points are totally connected with one another, and likewise for the
other $n$ points, and the two subgraphs are connected by one edge, which we
call the bridge. We take as convention that $m\geq n$.

######  Lemma 2.1.

Let $\Gamma=B_{m,n}$. Then $\Gamma$ is a MCPG if and only if $m,n>1$ or
$m\in\\{1,2\\},n=1$.

###### Proof.

Let $\Gamma=B_{m,n}$, where $m\geq n\geq 1$. It clearly has at least 2
vertices. The graph $\Gamma$ is also connected because the two complete
subgraphs are linked by an edge.

Next, we will show that $\overline{\Gamma}$ is 2-colorable. In fact something
stronger is true - obviously $\overline{\Gamma}$ is the complete bipartite
graph with one edge removed. The fact that $\overline{\Gamma}$ is 2-colorable
implies it is triangle-free.

Finally, we want to show that if we remove any edge from $\Gamma$, (at least)
one of the first three conditions in the definition of minimally connected
prime graphs is violated. Removing the bridge edge results in a disconnected
graph.
Let $n>1$. Then removing an edge $\alpha\beta$ which is not the bridge edge,
combined with a vertex $\gamma$ which is not connected to either
$\alpha,\beta$ induces a triangle in the complement. Such a $\gamma$ exists
since $m\geq n>1$.

Next let $m\in\\{1,2\\},n=1$. Then the removal of any edge will result in a
disconnected graph.

Now let $\Gamma=B_{m,n}$ where $m>2,n=1$. Then $\Gamma$ contains $B_{m-1,2}$
as a proper subgraph, which corresponds to moving the bridge vertex over to
the other cluster. Thus the removal of an edge towards this subgraph
demonstrates that $\Gamma$ is not minimal. ∎

5142632’5’1’6’3’4’ Figure 1. The graph on the left is a MCPG where
$|V(\Gamma[\pi])|=|V(\Gamma[\sigma])=3$. The graph on the right is its
complement, where the primed points correspond to the numbered points on the
left. This demonstrates the point above—if we let the odd points be one color
(blue) and the evens be another (green), then the complement graph is seen to
be a 2-colorable hexagon, and all of the blue points are connected with all
the green points, excluding one edge.

Next, we will define some more notation. Let the set of MCPGs defined in Lemma
2.1 be denoted as $\mathcal{C}$.

From Theorem 2.1, it is natural to wonder whether a natural extension of
bridge having three disjoint, complete induced subgraphs can also be a MCPG,
but it is immediate to see that then one can pick vertices from each of the
three complete subgraphs which do not have any edge between them, so the
complement has a triangle.

Next we recall the notion of a minimal prime graph as it was defined in [8].

######  Definition.

A minimal prime graph is a graph $\Gamma$ with at least two vertices such that

  1. (1)

$\Gamma$ is connected

  2. (2)

$\overline{\Gamma}$ is triangle-free

  3. (3)

$\overline{\Gamma}$ is 3-colorable

  4. (4)

The removing of any edge results in a violation of at least one of the
conditions (ii) or (iii).

In particular, one can potentially remove an edge from a minimal prime graph
to attain a disconnected prime graph.

We let $\mathcal{G}$ denote the set of minimal prime graphs and
$\hat{\mathcal{G}}$ denote the set of minimally connected prime graphs. From
the similarity of the definitions we immediately get the following Lemma:

######  Lemma 2.2.

$\mathcal{G}\subsetneq\hat{\mathcal{G}}$

###### Proof.

Let $\Gamma$ be a minimal prime graph. Then removing any edge violates either
condition (ii) or (iii), so in particular we can see that removing any edge
violates either condition (i), (ii), or (iii). To see that the inclusion is
strict, consider the example in Figure 1. Removing the middle edge still
yields a prime graph but is disconnected. A simpler example is the connected
graph on 2 vertices.

∎

From here we can classify the graphs which are minimally connected prime
graphs but not minimal prime graphs. We will see that the graphs in
$\hat{\mathcal{G}}\setminus\mathcal{G}$ exactly take the form of complete
bridge graphs described in Theorem 2.1. We see that $\mathcal{C}$ is the set
of all complete bridge graphs, with some small exceptions.

######  Theorem 2.3.

Let $\Gamma\in\hat{\mathcal{G}}\setminus\mathcal{G}$. Then $\Gamma=B_{m,n}$
for some $m,n$ where $m\geq n>1$ or $m\in\\{1,2\\},n=1$.

###### Proof.

By $\Gamma\in\hat{\mathcal{G}}\setminus\mathcal{G}$, we note that there
necessarily exists an edge in $\Gamma$ such that, if removed, results in a
disconnected prime graph. Call the resulting connected components $\Gamma_{1}$
and $\Gamma_{2}$, and suppose that $\Gamma_{1}$ has $m$ vertices and
$\Gamma_{2}$ has $n$ vertices, with $m\geq n\geq 1$.

Suppose that $\Gamma_{1}$ is not a complete graph. If not, one can pick two
vertices $v_{1},v_{2}$ not linked by an edge, and another vertex
$u\in\Gamma_{2}$ which is not a bridge vertex, to form a triangle in the
complement. A similar reasoning applies to $\Gamma_{2}$. This shows that
$\Gamma=B_{m,n}$ and so we are done by Lemma 2.1. ∎

One desirable property of MCPGs, and our primary motivation in consdering such
graphs, is that they properly satisfy minimality. This is reflected in the
following Lemma, which assists us greatly in later describing the diameter in
Theorem 4.7.

######  Lemma 2.4.

Let $\Gamma$ be a MCPG with $n$ vertices. Then for any subgraph $\Lambda$
which satisfies (i), (ii), or (iii) on $n$ vertices, $\Lambda=\Gamma$.

One can think of this as minimality in the poset of connected prime graphs on
$n$ vertices.

###### Proof.

Suppose $\Lambda$ is a proper subgraph of $\Gamma$, i.e. it is missing an edge
in $\Gamma$. By $\Gamma$ being a MCPG, we have that removing this edge results
in a graph which (1) is disconnected, (2) has a triangle in the complement, or
(3) whose complement is not 3-colorable.
It is clear that removing more edges from $\Gamma$ cannot undo any of (1),
(2), or (3), which implies the assertion. ∎

######  Corollary 2.5.

Every MCPG on $n$ vertices can be attained by starting with the complete graph
on $n$ vertices and removing edges until the removal of any edge causes the
graph to violate (i), (ii), or (iii).

###### Proof.

This follows from the above minimality lemma and also from the fact that a
graph containing a minimal prime graph as a subgraph is itself a connected
prime graph. ∎

##  3\. Generating Prime Graphs

In this section, we will be considering what kind of graphs can be generated
from other graphs in $\mathcal{C},\mathcal{G}$, and (more broadly)
$\hat{\mathcal{G}}$. First, we define what it means for a graph to be
generated from another.

######  Definition.

We say a prime graph $\Gamma^{*}$ can be generated from another graph $\Gamma$
if we can construct $\Gamma^{*}$ from $\Gamma$ by adding one new vertex
$\alpha$ to $\Gamma$ and a collection of edges $\alpha\beta_{i}$, where
$\beta_{i}\in\Gamma$ for all $i$. In other words,
$|V(\Gamma^{*})|=|V(\Gamma)|+1$ and $\Gamma^{*}[V(\Gamma)]=\Gamma$, where
$\Gamma^{*}[V(\Gamma)]$ is the induced subgraph of $\Gamma^{*}$ on the
vertices of $\Gamma$.

######  Lemma 3.1.

If $\Gamma\in\mathcal{G}$, then $\Gamma$ can be used to generate another graph
$\Gamma^{*}\in\mathcal{G}$.

###### Proof.

This is proved as Proposition 3.1 in [8]. ∎

######  Lemma 3.2.

If $\Gamma\in\mathcal{C}$, then $\Gamma$ can be used to generate another graph
$\Gamma^{*}\in\mathcal{C}$.

###### Proof.

First note that by Theorem 2.3 that $\Gamma$ is a bridge graph $B_{m,n}$ with
$m,n>1$ or $m=1,2,n=1$. Then take one of the complete induced subgraphs,
either of size $m,n$ and increase its size by one. Except in the case where
$m=2,n=1$ and the subgraph chosen is the one of size $n$, this produces a
valid new bridge graph by Lemma 2.1. ∎

514263$\alpha$ Figure 2. This is an example of a graph that can be generated
from the MCPG in Figure 1. Here, we introduce the new point $\alpha$, which we
connect with all the odd-labeled vertices in the left induced subgraph to keep
it complete.

######  Corollary 3.3.

If $\Gamma\in\hat{\mathcal{G}}$, then $\Gamma$ can be used to generate another
graph $\Gamma^{*}\in\hat{\mathcal{G}}$.

###### Proof.

Suppose $\Gamma$ is a MCPG. By Theorem 2.3 we know that $\Gamma$ is either a
minimal prime graph or a complete bridge graph. If $\Gamma\in\mathcal{G}$,
then a new minimal prime graph $\Gamma^{*}$ can be generated from $\Gamma$ by
3.1, which is also a MCPG. If $\Gamma\in\mathcal{C}$, then a similar result
follows from Lemma 3.2. ∎

Corollary 3.3 used the fact that graphs in $\mathcal{G}$ can be used to
generate other graphs in $\mathcal{G}$ and similarly for graphs in
$\mathcal{C}$, but this provides us with the question: Can a graph in
$\mathcal{G}$ be used to generate a graph in $\mathcal{C}$? And how about in
the reverse direction? We answer these questions in the following two lemmas.

######  Lemma 3.4.

If $\Gamma\in\mathcal{C}$, where the two complete subgraphs of $\Gamma$ have
at least two vertices each, then $\Gamma$ can be used to generate another
graph $\Gamma^{*}\in\mathcal{G}$.

###### Proof.

Let $\Gamma\in\mathcal{C}$, as defined in the proposition. We introduce a new
vertex $\alpha$ and we add every edge $\alpha\beta$, where $\beta\in
V(\Gamma)$, excluding the bridge vertices $p$ and $q$. Let this new graph be
$\Gamma^{*}$, which we will show is in
$\hat{\mathcal{G}}\setminus\mathcal{C}$.

First, we will show $\Gamma^{*}\in\hat{\mathcal{G}}$. Clearly, $\Gamma^{*}$ is
connected because $\Gamma$ is connected and the vertex $\alpha$ has at least
two edges by our specifications on $\Gamma$. Also, we know
$E(\overline{\Gamma^{*}})=E(\overline{\Gamma})\cup\\{\alpha p\\}\cup\\{\alpha
q\\}$. The complement graph $\overline{\Gamma}$ is triangle-free because
$\Gamma\in\mathcal{C}$, and $\alpha,p$, and $q$ do not form a triangle because
$pq\not\in E(\overline{\Gamma})$. Hence, we conclude $\overline{\Gamma^{*}}$
is triangle-free. Additionally, it is easy to show that
$\overline{\Gamma^{*}}$ must be 3-colorable, which we know is a necessary
property of minimal prime graphs by Lemma 3.2 in the prime graphs paper. By
Theorem 2.3, we know that $\Gamma$ is a 2-connected graph, which implies that
$\overline{\Gamma}$ is 2-colorable. Because $\alpha$ is connected to vertices
in both of the complete subgraphs, it must be a different color than the two
used to color the points in the complement subgraphs. Hence,
$\overline{\Gamma^{*}}$ is three-colorable. Now, consider the graph
$\Gamma^{*}\setminus\\{ab\\}$. If $ab\in E(\Gamma)$ and $ab\neq pq$, then we
know $\overline{\Gamma^{*}}$ is not triangle-free because this will induce a
triangle in the subgraph $\overline{\Gamma}$. Next, suppose $ab=pq$. This
results in the triangle with vertices $\alpha,p$, and $q$ in the complement
graph. Finally, suppose $ab\in E(\Gamma^{*})\setminus E(\Gamma)$. Hence, we
can say $a=\alpha$. If $b$ is in the complete induced subgraph of $\Gamma$
containing $p$, then this creates the triangle of vertices $a,b,$ and $q$ in
the complement graph. If $b$ is in the other complete induced subgraph, then
we get the triangle of vertices $a,b,$ and $p$. Thus, removing any edge $ab$
from $\Gamma^{*}$ results in a triangle in
$\overline{\Gamma^{*}\setminus\\{ab\\}}$, so we can conclude
$\Gamma^{*}\in\hat{\mathcal{G}}$.

Finally, we must show that $\Gamma^{*}\setminus\\{ab\\}$ does not result in a
disconnected graph for any $ab\in E(\Gamma^{*})$. If we consider the subgraph
$\Gamma$, $pq$ is the only edge whose removal results in a disconnected graph.
This means that $\Gamma^{*}\setminus\\{ab\\}$, where $ab\in E(\Gamma)$ and
$ab\neq pq$, is still connected. Also, we find $\Gamma^{*}\setminus\\{pq\\}$
is still connected because $\alpha$ is connected to the two complete induced
subgraphs of $\Gamma$ at a minimum of one vertex each. Finally, we consider
$\Gamma^{*}\setminus\\{ab\\}$, where $ab\in E(\Gamma^{*})\setminus E(\Gamma)$
(so, once again, we can let $a=\alpha$). This graph is still connected because
the subgraph $\Gamma$ remains connected and $\alpha$ is connected to at least
two other vertices. Hence, we see that removing any edge of $\Gamma^{*}$ does
not result in a disconnected graph. However, for any graph in $\mathcal{C}$,
there is an edge whose removal results in a disconnected graph, so we deduce
$\Gamma^{*}\not\in\mathcal{C}$.

It follows from the results above that
$\Gamma^{*}\in\hat{\mathcal{G}}\setminus\mathcal{C}=\mathcal{G}$ (by Theorem
2.3) and $\Gamma^{*}$ has one more vertex than $\Gamma$. ∎

514263$\alpha$ Figure 3. This is a graph in $\mathcal{G}$ that can be
generated from the graph in Figure 1 through the method used in the proof of
Lemma 3.4.

By the formulation of the lemma, the smallest MCPG that we can apply this
construction method to is $B_{2,2}$. Whenever we do so, this produces the
5-cycle, which is the smallest MPG. In the following lemma, we show that there
is no analogous construction in the reverse direction.

######  Lemma 3.5.

If $\Gamma\in\mathcal{G}$, then $\Gamma$ cannot be used to generate some graph
$\Gamma^{*}\in\mathcal{C}$.

###### Proof.

Recall that by Lemma 3.2 in [8] we know that the complement of any graph in
$\mathcal{G}$ has chromatic number 3, whereas complements of graphs in
$\mathcal{C}$ are 2-colorable. This immediately implies the assertion. ∎

To summarize some our results on generation of graphs, we let $A\rightarrow B$
denote that "a prime graph in set $A$ can be used to generate a prime graph in
set $B$." Clearly, $A\not\rightarrow B$ denotes "a prime graph in set $A$
cannot be used to generate a prime graph in set $B$." This leads us to the
main theorem of this section.

######  Theorem 3.6.

The following list shows which types of primes graphs can be used to generate
other kinds of prime graphs:

  1. (1)

$\mathcal{G}\rightarrow\mathcal{G}$

  2. (2)

$\mathcal{C}\rightarrow\mathcal{C}$

  3. (3)

$\mathcal{C}\rightarrow\mathcal{G}$

  4. (4)

$\mathcal{G}\nrightarrow\mathcal{C}$.

###### Proof.

The theorem follows from Lemmas 3.1, 3.2, 3.4, and 3.5. ∎

These are all of the interesting combinations of the graph classes. Also, we
remind the reader that Corollary 3.3 shows that any MCPG can be used to
generate another MCPG, and we can deduce by Theorem 2.3 and Theorem 3.6 that
any MCPG can be used to generate a graph in $\mathcal{G}$, but it is not the
case that any MCPG can be used to generate a new graph in $\mathcal{C}$.

##  4\. The Diameters of Minimally Connected Prime Graphs

Recall that the diameter of a graph is the maximum distance between a pair of
vertices in the graph, where distance is the length of the shortest path. We
take as convention that disconnected graphs have infinite diameter. We first
consider the diameter of graphs in $\mathcal{C}$.

######  Proposition 4.1.

If $\Gamma\in\mathcal{C}$, then $\operatorname{diam}(\Gamma)\leq 3$. More
precisely, $\operatorname{diam}(B_{1,1})=1,\operatorname{diam}(B_{2,1})=2$,
and $\operatorname{diam}(B_{m,n})=3$ for $m\geq n>1$.

###### Proof.

This is immediately checked by the reader.

∎

We can conclude our study of the diameters of MCPGs by using an important
result from Lucido.

######  Lemma 4.2.

If $\Gamma\in\hat{\mathcal{G}}$, then $\operatorname{diam}(\Gamma)\leq 3$.

###### Proof.

Because $\Gamma\in\hat{\mathcal{G}}$, we know that $\overline{\Gamma}$ is
triangle-free and 3-colorable. By Theorem 2 in [8], we know that there is some
solvable group $G$ such that $\Gamma$ is isomorphic to the prime graph of $G$.
Lucido showed in [11] that the diameter of the prime graph of a solvable group
is less than or equal to 3, which establishes the lemma. ∎

######  Theorem 4.3.

For any prime graph $\Gamma$ with $\operatorname{diam}(\Gamma)=3$,
$\overline{\Gamma}$ is 2-colorable.

###### Proof.

By $\operatorname{diam}{\Gamma}=3$, there necessarily exist points $a$, $b$
such that the distance between $a$ and $b$ is 3.

Since $a,b$ are not connected in $\Gamma$ they are necessarily connected in
the complement, and thus also necessarily different colors. Let $a$ be colored
green, $b$ be colored blue.

Let $v$ be any another vertex. Then if $v$ is connected to neither $a$ or $b$
in $\bar{\Gamma}$, there exists a path of length $2$ from $a$ to $b$ in
$\Gamma$, $a\rightarrow v\rightarrow b$.

Suppose $v$ is connected to $a$ in $\bar{\Gamma}$. Then we can color $v$ blue.
Otherwise if $v$ is connected to $b$ in $\bar{\Gamma}$, we color $v$ green.
Note that $v$ cannot be connected to both, as otherwise there is a triangle
$(a,b,v)$.

We follow this procedure for all vertices which are not $a$ or $b$, and claim
this is a valid $2$-coloring of $\bar{\Gamma}$. To see why, suppose we have
two points $v_{1},v_{2}$ which are both green under this construction. Then
$v_{1},v_{2}$ are connected to $b$ by construction. So $v_{1},v_{2}$ cannot be
connected, otherwise $\bar{\Gamma}$ contains a triangle $(v_{1},v_{2},b)$. A
similar reasoning holds if $v_{1},v_{2}$ are both blue. ∎

######  Corollary 4.4.

For $\Gamma\in\mathcal{G}$, $\operatorname{diam}{\Gamma}=2$.

###### Proof.

This follows from Theorem 4.3 and the fact that MPGs have chromatic number 3,
from [8]. ∎

######  Lemma 4.5.

Let $\Gamma$ be any undirected graph, and let $\Gamma^{\prime}$ be attained
from $\Gamma$ via removing an edge. Then
$\operatorname{diam}(\Gamma^{\prime})\geq\operatorname{diam}(\Gamma)$

###### Proof.

This is immediate from considering the definition of diameter - removing edges
cannot decrease the diameter, only increase it. ∎

######  Lemma 4.6.

Let $\Gamma$ be a connected prime graph. Then $\operatorname{diam}(\Gamma)=3$
if and only if any sequence of edge removals on $\Gamma$ to reach a MCPG ends
in a complete bridge graph.

###### Proof.

First recall that we can remove edges until reaching a MCPG by MCPGs
satisfying the proper minimality conditions in Lemma 2.4 and Corollary 2.5.

Let $\Gamma$ be a prime graph such that there exists a sequence of edge
removals to reach a minimal prime graph, which has diameter 2 by 4.4. Then it
follows from Lemma 4.5 that $\operatorname{diam}(\Gamma)\leq 2$, so in
particular $\Gamma$ cannot be a minimal prime graph. The theorem follows from
our discussion on the set-difference between MCPGs and MPGs. ∎

The following theorem characterizes prime graphs of solvable groups via our
results so far.

######  Theorem 4.7.

Let $\Gamma$ be a prime graph. Then

  * (i)

$\Gamma$ is disconnected if and only if the disconnected components are
complete graphs

  * (ii)

$\operatorname{diam}(\Gamma)=1$ if and only if $\Gamma$ is a complete graph

  * (iii)

$\operatorname{diam}(\Gamma)=3$ if and only if every sequence of edge removals
towards a minimally connected prime graph results in a complete bridge graph

  * (iv)

Otherwise, $\operatorname{diam}(\Gamma)=2$

###### Proof.

$(i)$ follows from $\Gamma$ being triangle-free, so a disconnected graph must
have complete components.

$(ii)$ follows easily from the definition of diameter.

$(iii)$ is from 4.6 ∎

##  5\. Hamiltonian Cycles and Paths in MCPGs

######  Proposition 5.1.

Any complete bridge graph contains a Hamiltonian path

###### Proof.

It is obvious that a complete bridge graph $B_{m,n}$ is not Hamiltonian. Even
though it contains two complete induced subgraphs, the single edge connecting
them renders it impossible for there to be a single cycle that includes every
vertex. However, we can find a path that connects all vertices. Let
$\\{u_{1},...,u_{m}\\}$ be the induced complete subgraph on $m$ vertices, and
$\\{v_{1},...v_{n}\\}$ be the complete induced subgraph on $n$ vertices, where
$u_{m},v_{n}$ are the bridge vertices. Then we can construct the following
path that reaches each vertex once: $u_{1}\rightarrow
u_{2}\rightarrow...\rightarrow u_{m-1}\rightarrow u_{m}\rightarrow
v_{n}\rightarrow v_{n-1}\rightarrow...\rightarrow v_{2}\rightarrow v_{1}$.
This is one such Hamiltonian path. ∎

It is well-known that the number of Hamiltonian paths for a graph of the form
$B_{n,n}$ (also known as a barbell graph) is $[(n-1)!]^{2}$ [1]. We generalize
by considering the number of Hamiltonian paths for an arbitrary complete
bridge graph.

######  Proposition 5.2.

The number of Hamiltonian paths on $B_{m,n}$ is $(m-1)!(n-1)!$.

###### Proof.

Consider the graph $\Gamma=B_{m,n}$. Any Hamiltonian path in $\Gamma$ must
contain the full Hamiltonian paths of the complete subgraphs, connected by the
bridge edge. The number of Hamiltonian paths for the complete graph $K_{n}$ is
$n!$, so we attain $m!$ and $n!$ Hamiltonian paths from each induced complete
subgraph. However, for a Hamiltonian path in $\Gamma$, we can say without loss
of generality that the path in one complete subgraph must end at the bridge
vertex and the other must start at the other bridge vertex. Thus, the number
of valid Hamiltonian paths in the two subgraphs are $(m-1)!$ and $(n-1)!$, so
when we consider all the Hamiltonian paths in $\Gamma$, we find that there are
$(m-1)!(n-1)!$ in total. ∎

Now, we are prepared to show that all MPGs are Hamiltonian.

######  Theorem 5.3.

If $\Gamma\in\mathcal{G}$, then $\Gamma$ is Hamiltonian.

###### Proof.

First recall from Lemma 4.1 of [8] that all MPGs contain an induced 5-cycle.
By some simple casework on the complement’s coloring, we see that we can
assume without loss of generality that 2 are green, 2 are blue, 1 is yellow,
and they are labeled and connected as in Figure 4.

$g_{1}$$g_{2}$$b_{1}$$b_{2}$$y_{1}$ Figure 4. A 3-coloring of the complement
of the induced 5-cycle in a minimal prime graph, superimposed on the 5-cycle

Since green vertices cannot be connected by a edge in the complement, we see
that they are fully connected amongst one another in $\Gamma$, and similarly
for the blue and yellow vertices themselves.
Let $\mathfrak{G}$ denote the set of green vertices, $\mathfrak{B}$ the blue
vertices, and $\mathfrak{Y}$ the yellow vertices. Let the vertices be as
labeled in the diagram. Suppose $\Gamma$ contains only that yellow vertex,
$y_{1}$. Then we can create a Hamiltonian cycle as follows - start at $g_{1}$,
go through every green vertex and end at $g_{2}$, then go to $b_{2}$, then go
through every blue vertex ending on $b_{1}$, then go to $y_{1}$, and then back
to $g_{1}$. This can be visualized as below:

$g_{1}\rightarrow\text{ every other green vertex }\rightarrow g_{2}\rightarrow
b_{1}\rightarrow\text{ every other blue vertex }\rightarrow b_{2}\rightarrow
y_{1}\rightarrow g_{1}$

So now suppose there are other yellow vertices. If any yellow vertex $y$ is
connected to $g_{1}$ then we have a Hamiltonian cycle as

$g_{1}\rightarrow\text{ every other green vertex }\rightarrow g_{2}\rightarrow
b_{1}\rightarrow\text{ every other blue vertex }\rightarrow b_{2}\rightarrow
y_{1}$ $\rightarrow\text{ every other yellow vertex }\rightarrow y\rightarrow
g_{1}$

So now suppose no other yellow vertex $y$ is connected to $g_{1}$. By
considering the triangles $(y,g_{1},b_{1})$, $(y,g_{1},b_{2})$ we see that all
other yellow vertices $y$ are connected to $b_{1}$ and $b_{2}$.
So then we can take the path

$g_{1}\rightarrow\text{ every other green vertex }\rightarrow g_{2}\rightarrow
b_{1}\rightarrow\text{ every other blue vertex }\rightarrow b_{2}\rightarrow
y$ $\rightarrow\text{ every other yellow vertex }\rightarrow y_{1}\rightarrow
g_{1}$

Thus $\Gamma$ is Hamiltonian. ∎

Figure 5. An example of a solvable group prime graph which contains a complete
bridge graph and is not Hamiltonian

Like in Theorem 4.7, where minimality let us classify the prime graphs of
solvable groups, we have a similar result for the Hamiltonian property. First
note that a graph which is Hamiltonian after edge removals is Hamiltonian
prior to the edge removals. So the only non-Hamiltonian prime graphs are those
which contain a complete bridge graph (See Figure 5), and all extra edges
share the same bridge vertex. If not, then a Hamiltonian cycle can be found.
This leads to the following theorem:

######  Theorem 5.4.

Let $\Gamma$ be a solvable group prime graph. Then $\Gamma$ is not Hamiltonian
if and only if it is disconnected with 2 complete components, or contains a
complete bridge graph and any extra edges share the same bridge vertex.

##  6\. Minimally Connected Prime Graphs That Are Self-Complementary

######  Lemma 6.1.

If $\Gamma\in\mathcal{C}$ and $\Gamma$ is self-complementary, then
$\Gamma=B_{2,2}$.

###### Proof.

We know that $\mathcal{C}$ consists of the complete bridge graphs, $B_{1,1}$,
$B_{2,1}$, and $B_{m,n}$, where $m\geq n>1$. From Observation 1 of [5], we see
that if $\Gamma$ is a self-complimentary graph, then $|V(\Gamma)|\equiv 0$ or
$1\pmod{4}$. This immediately rules out $B_{1,1}$ and $B_{2,1}$, so we will
continue by only considering the graphs where $m,n>1$.

If either $m,n\geq 3$ then we see that $B_{m,n}$ has $K_{3}$ as a subgraph,
and thus has chromatic number at least $3$. However, we saw in [7] that the
complement of $B_{m,n}$ is 2-colorable, thus $B_{m,n}$ cannot be self-
complementary when $m\geq 3$ or $n\geq 3$. One can easily check by hand that
$B_{2,2}$ is self-complementary. ∎

######  Lemma 6.2.

If $\Gamma\in\mathcal{G}$ and $\Gamma$ is self-complementary, then
$\Gamma=C_{5}$ (the 5-cycle).

###### Proof.

Suppose $\Gamma\in\mathcal{G}$ and $\Gamma$ is self-complementary. We know
$\overline{\Gamma}$ is triangle-free, so $\Gamma$ must also be triangle-free
in order to be isomorphic to its complement.

Suppose that $|V(\Gamma)|\geq 6$. Then either $\Gamma$ or $\overline{\Gamma}$
has a triangle, corresponding to the simple Ramsey theory fact that
$R(3,3)=6$.

By examination we note that the only MPG on $5$ vertices is $C_{5}$, so thus
$\Gamma=C_{5}$. ∎

We use these two lemmas to conclude this section with its main theorem.

######  Theorem 6.3.

The only two self-complementary graphs in $\hat{\mathcal{G}}$ are $B_{2,2}$
and $C_{5}$.

###### Proof.

This follows immediately from Lemma 6.1 and Lemma 6.2 ∎

##  7\. Enumeration of Reseminant Graphs

We first define a family of minimal prime graphs first described in [8].

######  Definition.

We say that a graph is reseminant if it can be generated from the 5-cycle via
repeated vertex duplication. We let $\mathcal{R}$ denote the set of reseminant
graphs.

These reseminant graphs were originally considered in [8], where it was shown
that reseminant graphs are minimal prime graphs. The goal of this section is
to generalize and enumerate reseminant graphs.

Note that there exist minimal prime graphs which are not reseminant. One such
example is on 8 vertices, illustrated below in Figure 6. To see it is not
reseminant note that no vertex is a duplicate of another. To generalize the
idea of reseminant graphs, we take the following definition:

Figure 6. A non-reseminant minimal prime graph, on 8 vertices

######  Definition.

A graph $\Gamma$ is a base graph if no two vertices are ’identical’ - adjacent
with the same adjacency relations to the other vertices. Given a vertex, we
refer to the set of all vertices it is identical to, along with itself, as its
cluster.

Another way of understanding base graphs is that its maximum cluster size is
$1$.

######  Example 7.1.

The 5-cycle is a base graph. Its automorphism group is $D_{10}$.

######  Definition.

Given a base graph $\Gamma$, the set of $\Gamma$-reseminant graphs are those
graphs which can be obtained from $\Gamma$ via a finite sequence of vertex
duplications.

######  Definition.

Given a graph $\Gamma$, define its base to be the induced subgraph given by
picking one vertex in each of its clusters.

######  Proposition 7.2.

The following properties are true:

  1. (1)

Taking the base of a graph is a well-defined operation on graphs

  2. (2)

Two isomorphic graphs have isomorphic base graphs

  3. (3)

Let $\Gamma$ be a base graph. Then the base of a $\Gamma$-reseminant graph is
$\Gamma$.

###### Proof.

To see that taking the base is well-defined, note that picking any vertex in a
cluster results in the same graph. This holds since the adjacency relations of
two vertices in the same cluster are the same, via being identical.

Given two isomorphic graphs, since taking the base graph is an operation only
dependent on the adjacency relations of the graph, they must have isomorphic
base graphs.

Let $\Gamma$ be a base graph, and suppose we have a $\Gamma$-reseminant graph
$\hat{\Gamma}$. Then for each vertex $v$ in $\Gamma$, $\hat{\Gamma}$ has a
cluster for $v$ with size dependent on the number of vertex duplications done
on $v$. It remains to prove that two clusters cannot be merged via the
operation of vertex duplication. Let $v,v^{\prime}$ be vertices in $\Gamma$.
Then without loss of generality there exists a vertex $x$ that $v$ is
connected to but $v^{\prime}$ is not. Since vertex duplication duplicates
adjacency relations, each vertex in the cluster of $v$ will be connected to
each vertex in the cluster of $x$ in $\Gamma$, and no vertex in the cluster of
$v^{\prime}$ will be connected to a vertex in the cluster of $x$. This shows
that the cluster of $v$ and $v^{\prime}$ in $\hat{\Gamma}$ are distinct. ∎

######  Lemma 7.3.

Let $\Gamma$ and $\Lambda$ be base graphs. Let $\hat{\Gamma}$ be a
$\Gamma$-reseminant graph, and identify $\Gamma$ as a subgraph of
$\hat{\Gamma}$ via taking a base. Let $\hat{\Lambda}$ be a
$\Lambda$-reseminant graph. Given an isomorphism
$\phi:\hat{\Gamma}\to\hat{\Lambda}$, the image of $\Gamma$ under $\phi$ is a
base of $\Lambda$.

Conversely given an isomorphism $\psi:\Gamma\to\Lambda$ where $\Lambda$ is a
base of $\hat{\Lambda}$, $\psi$ extends to an isomorphism
$\hat{\psi}:\hat{\Gamma}\to\hat{\Lambda}$ if for every vertex $v\in\Gamma$,
the size of the cluster of $v$ is equal to the size of the cluster of
$\psi(v)$ in $\hat{\Lambda}$

###### Proof.

Consider the image $\phi(\Gamma)$. Suppose $v_{1},v_{2}$ in this image are in
the same cluster. Then they are in the same cluster in $\Gamma$, a
contradiction. Thus the image is a base graph.

Now suppose we have an isomorphism $\psi:\Gamma\to\Lambda$ as described, and
that for every vertex $v\in\Gamma$, the size of the cluster of $v$ is equal to
the cluster of $\psi(v)$ in $\hat{\Lambda}$. We can define the isomorphism
$\hat{\psi}:\hat{\Gamma}\to\hat{\Lambda}$ which extends $\psi$ by taking, for
each $v\in\hat{\Gamma}$ the cluster of $v$ to the cluster of $\psi(v)$
bijectively. This defines a graph map on the entirety of $\hat{\Gamma}$ since
$\Gamma$ is the base of $\hat{\Gamma}$. It is easy to verify the adjacency
relations are preserved, thus $\hat{\psi}$ is an isomorphism. ∎

From here we have the tools to prove more general statements analogous to
those proven about the 5-cycle as a base graph.

######  Lemma 7.4.

Let $\Gamma$ be a base graph, with $n$ vertices, which are numbered $1,...,n$.
Then a finite sequence $R_{m}$ of numbers with range $\\{1,...,n\\}$ defines a
$\Gamma$-reseminant graph given by performing the duplications according to
the sequence, and every $\Gamma$-reseminant graph can be defined in this way.

###### Proof.

The process for going from a sequence $R_{m}$ to a $\Gamma$-reseminant graph
is clear. To see this obtains all $\Gamma$-reseminant graphs, note that given
a $\Gamma$-reseminant graph $\hat{\Gamma}$, we can identify its base $\Gamma$
inside the graph of $\Gamma^{\prime}$ by taking the induced subgraph given by
picking one vertex from each cluster, as in 7.2. Then any vertex $v^{\prime}$
lives inside the cluster of some vertex $v$ of $\Gamma$ (identified as a
subgraph of $\Gamma^{\prime}$), and performing a vertex duplication on
$v^{\prime}$ is the same as performing a vertex duplication on $v$, since they
lie in the same cluster. ∎

######  Lemma 7.5.

Let $R_{m}$, $S_{m}$ be two sequences that define a $\Gamma$-reseminant graph.
$R_{m}$ and $S_{m}$ define the same reseminant graph if some reordering of the
sequence $R_{m}$ yields $S_{m}$.

###### Proof.

Take the identity isormophism on $\Gamma$. This extends to an isomorphism via
lemma 7.3 since their vertex cluster sizes are the same. ∎

######  Theorem 7.6.

Consider the automorphism graph of $\Gamma$, $Aut(\Gamma)$ as a subgroup of
$S_{n}$, based on its action on the labeled vertices. Let $Aut(\Gamma)$ act on
the set of n-tuples via the induced action from $S_{n}$. Then two n-tuples
define isomorphic $\Gamma$-reseminant graphs if and only if they lie in the
same orbit.

###### Proof.

First suppose that two n-tuples $(a_{1},...,a_{n})$ and $(b_{1},...,b_{n})$
lie in the same orbit, ie there exists $\sigma\in Aut(\Gamma)$ such that
$\sigma(a_{1},...,a_{n})=(b_{1},...,b_{n})$. Then $\sigma$ is an isomorphism
on the base graph of each $\Gamma$-reseminant graph, and it extends to an
isomorphism via lemma 7.3 since lying in the same orbit tells us $\sigma$
satisfies the proper cluster size condition.

Now suppose that two n-tuples define isormophic $\Gamma$-reseminant graphs.
Given an isomorphism $\phi$, which is an isomorphism when restricted to
$\Gamma$, call it $\varphi$. The image $\phi(\Gamma)$ is necessarily also
$\Gamma$. In addition, it holds that for every vertex $v$ in $\Gamma$, its
cluster size is equal to the cluster size of $\phi(v)$. Thus taking $\varphi$
shows that the two $n$-tuples lie in the same orbit. ∎

######  Corollary 7.7.

Let $Aut(\Gamma)$ act on the set of non-negative n-tuples with sum $k$. Then
the number of $\Gamma$-reseminant graphs on $n+k$ vertices is equal to the
number of orbits of that action.

###### Proof.

This follows easily from the fact that the elements of $Aut(\Gamma)$ do not
change the sum of the n-tuple, so the set of non-negative n-tuples can be
restricted to those yielding graphs with $n+k$ vertices. ∎

For a particular $\Gamma$, we can compute the exact number via a standard
orbit counting argument (Cauchy-Frobenius formula, also often (falsely)
referred to as Burnside’s Lemma). We do this for the 5-cycle to count all
reseminant graphs.

######  Corollary 7.8.

The number of reseminant graphs on $n+5$ vertices is given by

  * •

$\cfrac{\binom{n+4}{n}+4+\frac{5n^{2}+30n+40}{8}}{10}$ if $2\mid n,5\mid n$

  * •

$\cfrac{\binom{n+4}{n}+\frac{5n^{2}+30n+40}{8}}{10}$ if $2\mid n,5\nmid n$

  * •

$\cfrac{\binom{n+4}{n}+4+\frac{5n^{2}+20n+15}{8}}{10}$ if $2\nmid n,5\mid n$

  * •

$\cfrac{\binom{n+4}{n}+\frac{5n^{2}+20n+15}{8}}{10}$ if $2\nmid n,5\nmid n$

###### Proof.

Let $X$ denote the set of non-negative 5-tuples $(a,b,c,d,e)$ such that their
sum is $n$. Then $D_{10}$ acts on $X$ via considering $D_{10}$ as a subset of
$S_{5}$. We wish to count the orbits of this action.

We use the Cauchy-Frobenius orbit counting formula which states that the
number of orbits is the the average number of fixed points, ie that

(1) $|X/D_{10}|=\frac{1}{|D_{10}|}\sum_{\sigma\in D_{10}}|X^{\sigma}|$

Note that $X$ has size $\binom{n+5-1}{n}$, computed using a standard
combinatorial counting argument (:balls & boxes"). Consider the elements of
$D_{10}$. We have

  * •

1 identity element which fixes all elements of $X$

  * •

4 different rotations which fix an element if $n\equiv 0\text{ mod }5$

  * •

5 reflections, which fix $\frac{n^{2}+6n+8}{8}$ elements if $n$ is even,
$\frac{n^{2}+4n+3}{8}$ elements if $n$ is odd

To see this, note that the non-trivial rotations fix an element if and only if
all 5 of its indices are equal.

For a given reflection, consider the value of the fixed index to be $i$. Then
$n-i$ must be even, and we get a fixed point for each pair $x,y$ such that
$x+y=\frac{n-i}{2}$. Here, $x,y$ represent the values of the other 2 indices
on one side of the reflection, and together with $i$ determine the 5-tuple, as
illustrated in the figure. The number of such pairs $x,y$ is simply
$\frac{n-i}{2}+1$, so together with some casework on the parity

$\displaystyle n\text{ even }$ $\displaystyle\sum_{2|i,0\leq i\leq
n}\frac{n-i}{2}+1=\frac{n^{2}+6n+8}{8}$ $\displaystyle n\text{ odd }$
$\displaystyle\frac{(n-1)^{2}+6(n-1)+8}{8}=\frac{n^{2}+4n+3}{8}$

this yields the above expressions. Then plugging into (1) yields the
corollary. ∎

We mention here that Corollary 7.7 was also obtained in Summer 2018 during a
six week research project by a research team of (at the time) three high
school students - Joshua Kolenbrander, Elijah Stroud, Selina Wu - under the
guidance of the fourth author as part of the Honors Summer Math Camp at Texas
State University. The team came up with the alternative (but equivalent)
formula

$\left\lfloor\frac{n^{4}}{240}+\frac{n^{3}}{24}+\frac{5n^{2}}{24}+\frac{n}{16}(-1)^{n}+\frac{25n}{48}\right\rfloor+1$

for the number of reseminant graphs on $n$ vertices. Their proof rested on the
observation that the number of reseminant graphs is the number of bracelets on
$n$ beads where exactly 5 beads (corresponding to the original 5-cycle) are
black. It was also during this project that the term "reseminant" was coined.

##  8\. Asymptotic Enumeration

Though we enumerated the family of reseminant graphs in Section 7, enumerating
minimal prime graphs in general is more difficult. We find an enumerative
connection of maximal triangle-free, 3-colorable graphs, and utilize a
folklore construction to attain a asymptotic lower bound. To do this, we
consider a third notion of minimality, which removed the condition of being
connected.

######  Definition.

A graph $\Gamma$ is a possibly disconnected minimal prime graph (PDMPG) if

  1. (1)

$\overline{\Gamma}$ is triangle-free

  2. (2)

$\overline{\Gamma}$ is 3-colorable

  3. (3)

removing any edge from $\Gamma$ results in a violation of (i) or (ii)

We denote the class of such graphs as $\tilde{\mathcal{G}}$.

Essentially we are loosening the definition of minimal prime graphs to allow
disconnected graphs. We immediately can characterize those graphs which lie in
the set-difference, in other words the disconnected minimal prime graphs, as
follows.

######  Lemma 8.1.

Let $\Gamma$ be such that it is a possibly disconnected minimal prime graph
but not a minimal prime graph. Then $\Gamma$ is disconnected with 2 completely
connected components.

###### Proof.

Let $\Gamma$ be such a graph. Then it is necessarily disconnected. If it has
more than 2 disconnected components one can form a triangle in the complement.

Now consider these two disconnected components. It necessarily holds that each
is complete, otherwise one can utilize the missing edge and a vertex from the
other component to form a triangle in the complement. ∎

Thus we can get a counting relation between the two types of graphs. Let
$\mathcal{G}_{k}$ denote the set of minimal prime graphs on $k$ vertices, and
$\tilde{\mathcal{G}}_{k}$ be defined similarly.

######  Corollary 8.2.

$|\tilde{\mathcal{G}}_{k}\setminus\mathcal{G}_{k}|=\lfloor\frac{k-1}{2}\rfloor.$

###### Proof.

By Lemma 8.1, $|\tilde{\mathcal{G}}_{k}\setminus\mathcal{G}_{k}|$ is equal to
the number of graphs with 2 disconnected complete components. The corollary
follows from casework on the parity of $k$ and counting pairs of positive
numbers $(a,b)$ such that $a+b=k$ and $a\neq b$. ∎

######  Corollary 8.3.

Let $\hat{\mathcal{G}}_{k}$ denote the number of minimally connected prime
graphs on $k$ vertices. Then if $k>3$,
$|\hat{\mathcal{G}}_{k}\setminus\mathcal{G}_{k}|=\lfloor\frac{k-1}{2}\rfloor-1.$
When $k\leq 3$,
$|\hat{\mathcal{G}}_{k}\setminus\mathcal{G}_{k}|=\lfloor\frac{k-1}{2}\rfloor.$

###### Proof.

Recall that by Theorem 2.3, the set difference are the complete bridge graphs
of the form $B_{m,n}$ for $m,n$ where $m\geq n>1$ or $m\in\\{1,2\\},n=1$. When
$k\geq 3$ we can assume that $m\geq n>1$.

Given a complete bridge graph $B_{m,n}$ with $m\geq n>1$ we can remove the
bridge edge to obtain a disconnected graph with 2 complete connected
components, with at least 2 vertices each. Conversely, given such a
disconnected graph, we can add a bridge edge between the two components to
obtain a complete bridge graph. This yields a set bijection to disconnected
graphs with 2 complete components with at least 2 vertices each. Since there
is only one exception in $|\tilde{\mathcal{G}}_{k}\setminus\mathcal{G}_{k}|$,
the graph with components of vertex size $1,k$, the corollary follows. The
case when $k\leq 3$ can be easily checked by hand. ∎

######  Definition.

A graph $\Gamma$ is a maximal triangle-free, 3-colorable graph if

  1. (1)

$\Gamma$ is triangle-free

  2. (2)

$\Gamma$ is 3-colorable

  3. (3)

Adding any edge to $\Gamma$ results in a violation of (i) or (ii)

We denote the class of such graphs by $\mathcal{H}$.

######  Proposition 8.4.

$\tilde{\mathcal{G}}$ is in bijection with $\mathcal{H}$ via taking the
complement. This bijection preserves vertex number.

One way to interpret the above results is the enumerating minimal prime graphs
is equivalent to enumerating maximal 3-colorable, triangle-free graphs. Given
one, one can find the other. Before exploring the enumerative connection, we
note that the bijection can be refined to minimal prime graphs.

######  Lemma 8.5.

The complement of a maximal triangle-free, 3-colorable graph $\Gamma$ with
chromatic number 3 is a minimal prime graph.

###### Proof.

We need to show that the complement of $\Gamma$, $\bar{\Gamma}$ is connected.
Suppose not - then $\bar{\Gamma}$ is disconnected but still a possible
disconnected minimal prime graph, so by 8.1 we see it is disconnected with 2
completely connected components. The complement of $\bar{\Gamma}$, returning
to $\Gamma$, is thus a complete bipartite graph, which is 2-colorable. ∎

Recall that it was proven that the complement of a minimal prime graph has
chromatic number 3 in [8, Lemma 2.3], which was used in Section 4. We give
another proof of this statement.

######  Lemma 8.6.

The chromatic number of the complement of a minimal prime graph $\Gamma$ is
$3$.

###### Proof.

We already have that the complement $\bar{\Gamma}$ is 3-colorable from the
definition. Suppose $\bar{\Gamma}$ is 2-colorable. Then we can assign such a
coloring, and note that the result is a subgraph of a complete bipartite
graph. It cannot be the complete bipartite graph itself because then $\Gamma$
is disconnected. So it is a subgraph of the complete bipartite graph. But if
there is more than 1 edge missing from being a complete bipartite graph, it
can be added without violating being triangle-free or 2-colorable. Thus there
is only one edge missing from being a complete bipartite graph, so the graph
is of class $\mathcal{C}$ which we already showed are not minimal prime
graphs. ∎

######  Theorem 8.7.

A graph $\Gamma$ is a minimal prime graph if and only if its complement is a
maximal triangle-free 3-colorable graph with chromatic number 3.

###### Proof.

This follows directly from the two above Lemmas. ∎

######  Remark.

The set of maximal triangle-free, 3-colorable graphs is not either a superset
or a subset of maximal triangle-free graphs. To see it is not a superset, take
the Groetzsch graph, which is maximal triangle-free. To see it is not be a
subset, note that a graph could be maximal triangle-free, 3-colorable but not
maximal triangle-free, if it has an edge which, when added, makes it chromatic
number 4 but does not add a triangle. Such a graph necessarily contains a pair
of vertices $v_{1},v_{2}$ with distance $\geq 3$ such that every 3-coloring of
the graph results in $v_{!},v_{2}$ having the same color. One such example, on
12 vertices, is given in [7].

######  Lemma 8.8.

The number of labeled maximal triangle-free, 3-colorable graphs on $n$
vertices is bounded below by $2^{(\frac{n^{2}}{8}+o(n^{2}))}$.

###### Proof.

We adapt the "folklore" construction described in [3]. A similar construction
can be found in [2].

Let $n$ be given. Take any bipartite graph with parts of size $n/4,n/2$, call
them $A$ and $B$ respectively. Then we embed it into a maximal triangle-free,
3-colorable graph, as follows. Take $A^{\prime}$ a set of $n/4$ vertices,
where for every $a\in A$ we introduce $a^{\prime}\in A^{\prime}$ which is
adjacent to $a$, and every vertex $b\in B$ such that $a$ and $b$ are not
adjacent.

This graph is triangle-free, and 3-colorable, if we let $A,A^{\prime},B$ be
the separate colors. However it might not be maximal with respect to those
properties.

An edge cannot be added between any two vertices $a_{1},a_{2}\in A$, as they
may have a mutual neighbor $b\in B$, which exists with proportion $1$ as
$n\to\infty$. Similarly an edge cannot be introduced between two vertices
$b_{1},b_{2}\in B$, due to a mutual neighbor $a\in A$. Given $a\in A,b\in B$,
the edge $a,b$ cannot be added, as this forms a triangle on
$(a,a^{\prime},b)$. Given $a^{\prime}\in A^{\prime},b\in B$ which are not
adjacent, $a^{\prime},b$ cannot be added as this similarly forms a triangle on
$(a,a^{\prime},b)$.

So any edge added to this graph must occur between a vertex in $A$ and a
vertex in $A^{\prime}$, or between vertices in $A^{\prime}$. However, we can
simply add such edges until the graph is maximal, 3-colorable, to see that we
have embedded our original bipartite graph in a maximal triangle-free,
3-colorable graph on $n$ vertices. Since there are $2^{\frac{n^{2}}{8}}$ such
graphs, this yields the lower bound of $2^{\frac{n^{2}}{8}+o(n^{2})}$ maximal
triangle-free, 3-colorable graphs. ∎

##  9\. Outlook

The bulk of this paper establishes various properties of prime graphs of
finite solvable groups, but much less is known about the prime graphs of
general finite groups. A few facts have been established - the prime graphs of
the simple groups are known [10], and a prime graph of a finite group cannot
be either a chain of length greater than 4 [12], or 5 disconnected points [4].
Generally speaking, very little is known about which graphs are realizable as
prime graphs of finite groups, which reflects the difficulty of understanding
finite groups in comparison with solvable groups. Nevertheless, properties of
prime graphs of solvable groups give rise to interesting conjectures and
questions about realizability of graphs as the prime graph of some finite
group. One such example is Maslova’s Conjecture [9], which she Gorshkov proved
for almost simple groups [6].

######  Conjecture 9.1 (Maslova’s Conjecture).

Given a finite group $G$ such that its prime graph does not contain
3-cocliques, its prime graph is isomorphic to the Gruenberg-Kegel graph of
some finite solvable group.

From our work, one can ask similar questions about finite groups, for example

  1. (1)

Is there a finite group $G$ such that its prime graph has more than 5 vertices
and is self-complimentary?

  2. (2)

Is there a finite group $G$ such that its prime graph is not Hamiltonian and
its complement has chromatic number $\geq 3$?

Another direction being explored, primarily by the second author, is the
spectral theory of the minimal prime graphs of finite solvable groups. This is
the content of a separate paper, titled The Adjacency Spectra of Some Families
of Minimally Connected Prime Graphs, being written at the time of writing.

We expect that the lower bound given by 8.8 should be sharp, since it is
exactly the asymptotic for maximal triangle-free graphs [2]. However, by the
prior remark, the set of maximal triangle-free, 3-colorable graphs is neither
a subset or a superset of maximal triangle-free graphs. Ideally, one might be
able to asymtotically approximate the maximal triangle-free, 3-colorable
graphs which are not maximal triangle-free by filling in the allowed edges
towards a maximal triangle-free graph. Although this process might over-count,
asymptotically we expect it should not be an issue.

##  10\. Acknowledgements

This research was conducted under NSF-REU grant DMS $1005206$ by the first,
second, third, and fifth authors during the Summer of 2020 under the
supervision of the fourth author. The authors graciously acknowledge the
financial support of NSF, as well as the hospitality of Texas State
University. In particular, Dr. Yong Yang, the director of the REU program, is
thanked for persevering despite the conditions created by the pandemic and
running the REU program in full.

## References

  * [1] Wolfram Alpha  “Barbell Graph”  URL: https://mathworld.wolfram.com/BarbellGraph.html
  * [2] József Balogh and Šárka Petříčková  “The number of the maximal triangle-free graphs”  In _Bull. Lon. Math. Soc._ 46.5, 2014, pp. 1003–1006
  * [3] “Determine or estimate the number of maximal triangle-free graphs on n vertices”, 2014  URL: https://mathoverflow.net/questions/159494/determine-or-estimate-the-number-of-maximal-triangle-free-graphs-on-n-vertices/160595#160595
  * [4] A.. Gavrilyuk, I.. Khramtsov, A.. Kondratév and N.. Maslova  “On realizability of a graph as the prime graph of a finite group”  In _Sib. Èlektron. Mat. Izv._ 11 Russian Academy of Sciences - RAS (Rossiı̆skaya Akademiya Nauk - RAN), Siberian Branch (Sibirskoe Otdelenie), Sobolev Insitute of Mathematics (Institut Matematiki Im. S. L. Soboleva), Novosibirsk, 2014, pp. 246–257
  * [5] Richard A. Gibbs  “Self-Complementary Graphs”  In _J. Comb. Theory_ B.16, 1974, pp. 106–123
  * [6] I.. Gorshkov and N.. Maslova  “Finite almost simple groups whose Gruenberg-Kegel graphs coincide with Gruenberg-Kegel graphs of solvable groups”  In _Algebra Logic_ 57.2 Springer US, New York, NY, 2018, pp. 115–129
  * [7] “Graph which is maximal triangle-free 3-colorable, but not maximal triangle-free”, MathOverflow, 2020  URL: https://mathoverflow.net/q/368994
  * [8] Alexander Gruber et al.  “A characterization of the prime graphs of solvable groups”  In _J. Algebra_ 442, 2015, pp. 397–422
  * [9] E.. Khukhro and V.. Mazurov  “Unsolved Problems in Group Theory. The Kourovka Notebook”  In _arXiv preprint arXiv:1401.0300v19_ , 2020
  * [10] A.. Kondratév  “Prime graph components of finite simple groups”  In _Mathematics of the USSR-Sbornik_ 67.1, 1990, pp. 235–247
  * [11] Maria Silvia Lucido  “The diameter of the prime graph of a finite group”  In _J. Group Theory_ 2.2, 1999, pp. 157–172
  * [12] I.. Zharkov  “On groups whose prime graph is a chain” In Russian, unpublished graduate work  Novosibirsk State University, 2008


11institutetext: L. Çelik, F. Ekmekçi, H. V. Şenavcı 22institutetext: Ankara
Univ., Faculty of Science, Dept. of Astronomy and Space Sciences, 06100,
Tandoğan, Ankara, Turkey, 22email<EMAIL_ADDRESS>33institutetext: J.
Nemec 44institutetext: Dept. of Physics & Astronomy, Camosun College,
Victoria, British Columbia, V8P 5J2, Canada, 55institutetext: K. Kolenberg
66institutetext: Harvard-Smithsonian Center for Astrophysics, 60 Garden St.,
Cambridge MA 02138 USA,
Instituut voor Sterrenkunde, Celestijnenlaan 200D, 3001 Heverlee, Belgium
77institutetext: J. Benkő, R. Szabó 88institutetext: Konkoly Obs. of the
Hungarian Academy of Sciences, Konkoly Thege Miklós út 15-17, H-1121 Budapest,
Hungary, 99institutetext: D. KURTZ 1010institutetext: D. Kurtz
1111institutetext: Jeremiah Horrocks Institute, Univ. of Central Lancashire,
Preston PR1 2HE, 1212institutetext: K. Kinemuchi 1313institutetext: Bay Area
Environmental Research Inst./NASA Ames Research Center, MS 244-30, Moffet
Field, CA 94035, USA

# How to Correctly Stitch Together Kepler Data of a Blazhko Star

L. Çeli̇k  F. Ekmekçi̇  J. Nemec  K. Kolenberg  J. M. Benkő  R. Szabó  D. W.
Kurtz  K. Kinemuchi  H. V. Şenavcı

###### Abstract

One of the most challenging difficulties that precedes the frequency analysis
of Kepler data for a Blazhko star is stitching together the data from
different seasons (quarters). We discuss the preliminary steps in the
stitching, detrending and rescaling process using the data for long-term
Blazhko stars. We present the process on Kepler data of a Blazhko star with a
variable Blazhko cycle and some first results of our analysis.

##  1 Stitching, Detrending and The Rescaling Process for Kepler

Several models have been proposed to explain the Blazhko effect (see e.g.,
Kolenberg2010 ) but it still remains a problem to be solved. An additional
difficulty for the analysis of Blazhko stars is that the data obtained in
subsequent quarters display some discrepancies in their flux values.
Therefore, when stitching together the light curves from different quarters,
these discrepancies must be removed.

To overcome the problems originating from Kepler itself and/or from the
“Automated Pipeline” routine, the users of the Kepler archive can use the
PyKEPyKE  software. In this study, we applied the rescaling process to five
Blazhko stars. After stitching the data for all quarters, the most notable
difference is the flux offset between subsequent quarters originating mainly
from the instrumental effects (see left panel of Fig. 1). Our rescaling
process matches the light curves from consecutive quarters. This matching is
based on the assumption that phase-ordered light curves with a few cycles
closest to each other between two consecutive quarters must have nearly the
same flux values at the same phases. The first parameter is the period of the
star. Another parameter, the folding epoch, must be determined to carry out
the phase ordering process. During the matching process, the corresponding
flux values for the same phases between phase-ordered light curves of two
consecutive quarters are determined and proportioned. Therefore, the phase
scaling factors are determined for, and applied to short ranges of phase. The
right panel of Fig. 1 represents a simple diagram of this approach for the
rescaling process.

Figure 1: The light curve of a Blazhko star, using the data from Q1 up to Q7
quarters without rescaling procedure (left panel), and with rescaling
procedure (right panel)

###### Acknowledgements.

We thank M. E. TÖRÜN (MSc) for his assistance during the software improvements
and thank the entire Kepler team for the efforts which have made these results
possible.

## References

  * (1) Kolenberg, K., Szabó, R., Kurtz, D. W., Gilliland, R. L. et al: First Kepler Results on RR Lyrae Stars. ApJL. 713, 198–203 (2010)
  * (2) http://keplergo.arc.nasa.gov/ContributedSoftwarePyKEP.shtml.Cited15Aug2011