40. S22 Effect of threshold to define return fixations. We repeated the analyses using thresholds of 1 dva (A-C), 2 dva (D-F), 3 dva (G-I), and 4 dva (J-L) to define return fixations. A, D, G, J. Proportion of return fixations (format as Fig. 8B). B, E, H, K. Distribution of return offsets for primates (format as Fig. 3J). C, F, I, L. Distribution of return offsets for the model (format as Fig. 8C).
  41. S23 Primates and our model tend to make longer saccades with larger turning angles. Relation between turning angle and saccade size for primates (A) and the model (B). Both primates and the model showed positive linear correlations between turning angles and saccade sizes.
  42. S24 Return fixation durations are longer for target compared to non-target locations. This figure expands upon and follows the same format as Figure 4A. Row 1: fixation durations for target locations. Row 2: fixation durations for non-target locations. Only visual search tasks are shown here because there are no target versus non-target locations during the free-viewing experiments.

## Main Figures

Fig 1: Primates make return fixations during natural vision. Example fixation
sequences (yellow circles) of humans (A-C) and monkeys (D) during visual
search (A), free viewing of static images (B, D), and a cooking task with a
head-mounted eye tracker (C) (see Fig. 2 for task definitions). The numbers
denote the fixation order. A fixation (yellow circles) is referred to as a
“return fixation” (red triangle) if the Euclidean distance to any of the
previous fixations is less than 1 degree of visual angle (dva). The previous
fixation overlapping with the return fixation is referred to as a “to-be-
revisited” fixation (red circle). There are two return fixations in B and one
in A, C, and D. E-F Return fixations are consistent across subjects. E and F
show example images of consistent return fixations across subjects in free
viewing tasks. Color bar on the right shows the scales of between- subject
consistency (see Fig. S5 for more examples).

Fig 2: Schematic description of the eight experimental paradigms. (A-C) Visual
search tasks with object arrays (A), natural images (B), and “Waldo” images
(C) (see [8] for details). (D-F) Free viewing experiments with static natural
images in humans (D) and monkeys (E, F). (G) Egocentric video dataset where
subjects had to follow various recipes to make breakfast (see [48] for
details). (H) Egocentric video dataset where subjects had to search for 22
items (see reference[49] for details). The numbers in the top right corner of
each subplot denote the total number of fixations (top) and the total number
of return fixations (bottom).

Fig 3: Human and non-human primates make frequent return fixations. (A-H)
Proportion of return fixations, i.e., total number of return fixations
normalized by total number of fixations, for each of the 8 experiments (Fig.
2). Each dot indicates an individual subject (horizontal spread is only for
visualization). The horizontal solid line shows the average across subjects.
The chance level (dashed lines) was computed by generating sequences of random
fixations (Methods). Asterisks indicate significant differences from chance
($p<0.05$, one-sample t-test). We did not conduct a statistical test in the
monkey free viewing 2 experiment as there were only 2 subjects. (I) Example
sequence of 8 fixations on an image, including return fixations (6, 7), to-be-
revisited fixations (3, 5), and non-return fixations (1, 2, 4, 8). The return
offset is the number of intervening fixations for a given return location. (J)
Distribution of the return offset for the 8 experiments. The light grey line
shows each subject and the black lines show averages. In the visual search
experiments, the solid and dashed lines show return fixations to non-targets
and targets, respectively.

Fig 4: Return fixations tended to last longer and follow smaller saccades. (A)
Duration of fixations in non-return fixation locations (dark gray), to-be-
revisited locations (black), and return fixation locations (light gray). Dots
show individual subjects. Error bars denote SEM. $\ast$ denotes $p<0.05$, two-
tailed t-test. The durations of return fixations tended to be longer for
return fixation locations in visual search tasks (see Fig. S24 for fixation
duration analysis separating target and non-target locations during visual
search. (B) Saccade size (same format as A). Return fixations tended to follow
smaller saccades.

Fig 5: Subjects tend to make more saccades with turning angles of 180 degrees
preceding return fixations. (A) Distribution of turning angles preceding
return fixations. Bin size = 12 degrees. The sharp peak at 180 degrees shows
that subjects often revert directions to return to their previously fixated
location with short offsets (Fig. 3). (B) Distribution of turning angles
preceding non-return fixations. Bin size = 12 degrees. The curves tend to show
a slight U-shape showing that subjects often either continue to move in the
same direction or else move in the opposite direction.

Fig 6: Return fixation locations depended on the image and task. (A) Return
locations tend to show higher saliency. Each dot shows a different subject.
$\ast$ denotes $p<0.05$, two-tailed t-test. To-be-revisited and return
locations overlap by definition, saliency at to-be-revisited locations was
similar to that at return locations and is not shown here. (B) During visual
search tasks, the proportion of return fixations was larger for target than
non-target locations. Gray asterisks denote a statistically significant
difference in the proportion of return fixations with respect to the chance
levels. Black asterisks denote a statistically significant difference between
target versus non-target locations. (C) Schematic of experiment to assess
whether return fixations shared similarity to the target. In each trial,
subjects were presented with an image (Target) and had to choose the more
similar image between two alternatives. There were three conditions: (1) Test,
where the two alternatives were return fixations versus non-return fixations,
(2) Control 1, where the two alternatives were an identical copy of the target
versus non-return fixations, and (3) Control 2, where the two alternatives
were a different object from the same category as the target versus non-return
fixations. (D) Accuracy in distinguishing images from each of the conditions
in C versus non-return fixations. Asterisks denotes statistically significant
difference from chance levels (horizontal dashed line at 50%, ($p<0.05$, one
sample t-test)).

Fig 7: Architecture of the computational model. (A) The model has a ventral
visual cortex module (pre-trained VGG-16) that extracts features from the
image. These features constitute the saliency map ($M_{sal})$. In visual
search tasks, the same ventral visual cortex module processes the target image
and modulates the features in the search image via top-down modulation,
generating a target similarity map ($M_{sim})$ [8]. See Fig S9 and Methods for
detailed architecture. (B) The generation of eye movements is governed by a
weighted combination of 4 maps: $M_{sal}$ (part A), $M_{sim}$ (part A, only in
visual search tasks), a time-dependent memory map ($M_{mem,t}$, and a time-
dependent saccade size constrain map ($M_{sac,t})$. At each time point $t$,
the 2D spatial memory decay map $M_{mem,t}$ is updated based on all previous
visited locations $\\{l_{1},l_{2},…,l_{t}\\}$. The brighter the color on the
memory decay map, the stronger the effect of memory inhibition. The saccade
size constrain map is also updated at each time point according to the current
fixation location, $l_{t}$. A winner-take-all chooses the maximum in the
combined attention map $M_{att,t}$ (yellow circle) as the location for the
next fixation. In visual search tasks, the model computes a recognition map
$M_{recog}$ indicating the confidence that the current fixation contains the
sought target (Fig S9B). If the target is found, the search stops; otherwise,
it continues. During free viewing tasks, the recognition map is not used and
the model keeps generating eye movements for a fixed amount of time.

Fig 8: The computational model generates return fixations. (A). Example
scanpaths by monkeys and by the model while free viewing natural images
(conventions follow those in Fig. 1.) (B) Proportion of return fixations. The
black dot denotes the proportion of return fixations for each subject
(reproduced from Fig. 3A-H). The red triangle denotes the proportion of return
fixations for the model. Black solid lines show average across subjects and
gray dashed lines show chance level. (C) Distribution of the return offset for
the model (format as in Fig. 3J).

Fig 9: The computational model captures return fixation turning angles and
saliency. Distribution of turning angles preceding return fixations (A) and
non-return fixations (B) for the model (format as in Fig. 5A-B). (C). Saliency
at return fixation locations and non-return fixation locations for the model
(format as in Fig. 6A).

## Supplementary Figures

Fig S1: Proportion of fixations that revisit the same location twice.
Following the format in Fig. 3, here we show the proportion of fixations that
return to the same location twice (as in the sequence
$L_{1}$-$L_{2}$-$L_{1}$-$L_{3}$-$L_{4}$-$L_{1}$ where $L$ indicates different
image locations). The black dots denote individual subjects (horizontal spread
added for visualization purposes only). Solid lines show average across
subjects. Asterisks indicate statistical significance with respect to chance.
($p<0.05$, one-sample t-test).

Fig S2: Extraction of fixations on egocentric videos. Egocentric videos (Fig.
2G-H) were analyzed in 5-second segments. (A). Distribution of normalized
Euclidian distance between the first frame and the last frame (solid lines).
The chance distribution of normalized Euclidian distance values was computed
by considering random pairs of frames from 100 different video sequences
(dashed line). Segments with large head motion (normalized Euclidian distance
$>$ 0.4, gray rectangle) were excluded from analyses. (B-C). Examples of the
first and last frame in 5-second clips (top) and extracted fixations (yellow
circles) mapped to the last frame of example video clips (bottom) during the
cooking task (B, Fig. 2G) and visual search (C, Fig. 2H). The figure
conventions follow Fig. 1.

Fig S3:  Proportion of return fixations among the first six fixations.
Following the format in Fig 3, here we show the proportion of return fixations
among the first six fixations of all scanpaths over all eight datasets.
Asterisks indicate statistical significance with respect to chance ($p<0.05$,
one-sample t-test).

Fig S4: Return fixations are consistent across subjects. (A). Example return
fixations over multiple subjects. The numbers indicate the fixation number in
the sequence for each subject. (B). The image is divided into a $32\times 40$
grid (only a few of the lines are shown in the image). For those locations
where there is at least one return fixation, we compute the proportion of the
total number of return fixations that land on that location (shown here by the
grayscale colormap). The entropy of the distribution is then computed from
those probability values. The lower the entropy, the higher the consistency
between subejcts. (C). Entropy for each experiment. Horizontal dashed lines
show the expected chance value obtained by assigning the total number of
return fixations to random locations for each image.

Fig S5: A. Example of consistent return fixations across subjects, Visual
Search 1.

Fig S5: B. Example of consistent return fixations across subjects, Visual
Search 2.

Fig S5: C. Example of consistent return fixations across subjects, visual
search 3.

Fig S5: D. Example of consistent return fixations across subjects, free
viewing (humans).

Fig S5: E. Example of consistent return fixations across subjects, free
viewing 1 (monkeys).

Fig S5: F. Example of consistent return fixations across subjects, free
viewing 2 (monkeys).

Fig S6: Distribution of saccade sizes. A. Distribution of saccade sizes for
humans and monkeys. B. Distribution of saccade sizes for the model.

Fig S7: Saccade sizes and angles for primates. Polar plot of distribution of
saccade sizes (radial coordinate) and angles for return fixations (A) and non-
return fixations (B) for humans and monkey experiments.

Fig S8: A. Return and non-return fixation locations. Locations of return
fixations (Columns 1, 3) and non-return fixations (Columns 2. 4) for each of
the experiments for humans/monkeys (Columns 1-2) and the model (Columns 3-4).
Each dot indicates the location of a return/non-return fixation.

Fig S8: B. Return and non-return fixation locations. Locations of return
fixations (Columns 1, 3) and non-return fixations (Columns 2. 4) for each of
the experiments for humans/monkeys (Columns 1-2) and the model (Columns 3-4).
Each dot indicates the location of a return/non-return fixation.

Fig S9: Calculation of bottom-up saliency map, target similarity map, and
recognition map in the computational model. (A). At the heart of the model is
a pre-trained deep convolutional network that mimics image processing along
the ventral visual cortex. Here we used the VGG-16 architecture [53]. The
features extracted from the top convolutional layer in the model yield the
saliency map, $M_{sal}$. During visual search tasks, we follow the work of
Zhang et al [8], to create a target similarity map, $M_{sim}$, based on
comparing the target features (orange box) and the search image features (gray
box). Only some of the layers are shown here for simplicity, the dimensions of
the feature maps are indicated for each layer. (B). For each location on the
search image, we cropped a fixation patch of size 224$\times$224 and used it
as input to the same pre-trained recognition network as (A) to extract the
feature maps. Similarly, we obtained the feature maps of the target image. We
computed the cosine similarity between the target and cropped features,
resulting in a 2D spatial recognition map $M_{recog}$ where each location on
the map denotes a confidence value of recognizing the target at each location
on $I_{S}$.

Fig S10: Memory decay function and 2D empirical distribution of saccade sizes.
(A). The memory decay is a function of the offset from the current fixation
(see Methods). (B). Saccade size prior maps ($M_{sac})$ for each of the
experiemnts. The map activation color scale is shown on the bottom left. In
all cases, we show the map assuming fixation in the center (yellow circle),
except in the first column where the map is shown assuming fixation in the
lower left (yellow circle).

Fig S11: Visualization examples of attention maps for the model. (A) Example
image. (B) Pattern of fixations predicted by the model. The plot follows the
conventions in Fig 1. (C) Saliency map ($M_{sal}$). (D) Similarity map
($M_{sim}$). ((E)) Saccade map ($M_{sac}$) for fixations 1, 3, 5 and 7. (F)
Memory map ($M_{map}$) for fixations 1, 3, 5 and 7. (G) Attention map
($M_{f})$ for fixations 1, 3, 5 and 7. The yellow circle indicates the
maximum, which corresponds to the fixation location.

Fig S12: Example return fixations in model predictions. Red-circles = to-be-
revisited locations. Red triangles = return fixations. The left column shows
data from humans and monkeys, the middle column shows return fixation
probability maps across all subjects (see color scale on bottom right), and
the rightmost column shows fixations for the model.

Fig S13: The model makes more return fixations at target locations than non-
target locations in visual search. Following the format in Fig. 6B, this
figure shows the proportion of return fixations in each visual search dataset
at target and non-target locations for the model. Asterisks denote statistical
significance above chance ($\ast$ denotes $p<0.05$, two-tailed t-test).

Fig S14: The model makes shorter saccades at return fixations than non-return
fixations. Following the format of Fig. 4B, bar plots show saccade sizes of
to-be-revisited, return, and non-return fixations for the computational model
over all static image datasets. Asterisks denote statistical significance
($\ast$ denotes $p<0.05$, two-tailed t-test).

Fig S15: Saccade sizes and turning angles for the model. Polar plot of
distribution of saccade sizes (radial coordinate) and turning angles preceding
return fixations (A) and non-return fixations (B) for the model.

Fig S16: Model ablations reveal critical model components. (A). Proportion of
return fixations for subjects (gray), full model (red), and three ablated
models (see text for details about each ablation). (B). Similarity index for
return fixations between models and experimental data.

Fig S17: Effect of model ablations on return offset. (A). Distribution of
return offsets for primates, default model, and ablated models. (B).
Similarity index for return offsets between models and experimental data.

Fig S18: Effect of model ablations on saccade size distribution. (A). Saccade
size distribution for primates, default model, and ablated models. (B).
Similarity index for saccade sizes between models and experimental data.

Fig S19: Effect of model ablations on turning angles. (A-B). Turning angle
distribution for return fixations (A) and non-return fixations (B) for
primates, default model, and ablated models. (C). Similarity index for turning
angles between models and experimental data preceding return fixations (left)
and non-return fixations (right).

Fig S20: Effect of model ablations on saliency at fixated locations. (A).
Saliency plot for primates and models at return (left) and non-return (right)
fixations. (B). Similarity index plot of saliency between primates and all
computational models for return (left) and non-return (right) fixations.

Fig S21: False negative and positive rates for humans and the model in Visual
Search 2 on natural images (A) and in Visual Search 3 on Waldo images (B). In
visual search tasks, the model has to decide whether the current fixation
patch is the target. We introduced the recognition map indicating the
confidence value of recognizing that fixation patch belongs to the target (see
Fig. S9B for recognition map $M_{recog}$ calculation). We empirically set a
threshold for deciding whether the target is found based on the corresponding
confidence value obtained from $M_{recog}$ at current location $l_{t}$. The
false positive rates for humans are defined as the number of mouse clicks at
the wrong locations normalized by total number of mouse clicks over all the
trials. The false negative rates for humans are defined as the proportion of
number of fixations falling on the targets and yet, humans do not recognize
the targets and continue to move their eyes to other locations out of total
number of fixations over all the trials. For the model, since the fixations
and the mouse clicks are always consistent, we calculated both false positive
rates and false negative rates based on the empirical thresholds and
normalized them based on total number of fixations.

Fig S22: Effect of threshold to define return fixations. We repeated the
analyses using thresholds of 1 dva (A-C), 2 dva (D-F), 3 dva (G-I), and 4 dva
(J-L) to define return fixations. A, D, G, J. Proportion of return fixations
(format as Fig. 8B). B, E, H, K. Distribution of return offsets for primates
(format as Fig. 3J). C, F, I, L. Distribution of return offsets for the model
(format as Fig. 8C).

Fig S22: Effect of threshold to define return fixations. We repeated the
analyses using thresholds of 1 dva (A-C), 2 dva (D-F), 3 dva (G-I), and 4 dva
(J-L) to define return fixations. A, D, G, J. Proportion of return fixations
(format as Fig. 8B). B, E, H, K. Distribution of return offsets for primates
(format as Fig. 3J). C, F, I, L. Distribution of return offsets for the model
(format as Fig. 8C).

Fig S22: Effect of threshold to define return fixations. We repeated the
analyses using thresholds of 1 dva (A-C), 2 dva (D-F), 3 dva (G-I), and 4 dva
(J-L) to define return fixations. A, D, G, J. Proportion of return fixations
(format as Fig. 8B). B, E, H, K. Distribution of return offsets for primates
(format as Fig. 3J). C, F, I, L. Distribution of return offsets for the model
(format as Fig. 8C).

Fig S22: Effect of threshold to define return fixations. We repeated the
analyses using thresholds of 1 dva (A-C), 2 dva (D-F), 3 dva (G-I), and 4 dva
(J-L) to define return fixations. A, D, G, J. Proportion of return fixations
(format as Fig. 8B). B, E, H, K. Distribution of return offsets for primates
(format as Fig. 3J). C, F, I, L. Distribution of return offsets for the model
(format as Fig. 8C).

Fig S23: Primates and our model tend to make longer saccades with larger
turning angles. Relation between turning angle and saccade size for primates
(A) and the model (B). Both primates and the model showed positive linear
correlations between turning angles and saccade sizes.

Fig S24: Return fixation durations are longer for target compared to non-
target locations. This figure expands upon and follows the same format as
Figure 4A. Row 1: fixation durations for target locations. Row 2: fixation
durations for non-target locations. Only visual search tasks are shown here
because there are no target versus non-target locations during the free-
viewing experiments.


#  On balanceable and simply balanceable regular graphs

Milad Ahanjideh
FAMNIT and IAM, University of Primorska, Koper, Slovenia
<EMAIL_ADDRESS>Martin Milanič
FAMNIT and IAM, University of Primorska, Koper, Slovenia
<EMAIL_ADDRESS>Mary Servatius
Koper, Slovenia
<EMAIL_ADDRESS>
###### Abstract

We continue the study of balanceable graphs, defined by Caro, Hansberg, and
Montejano in 2021 as graphs $G$ such that any $2$-coloring of the edges of a
sufficiently large complete graph containing sufficiently many edges of each
color contains a balanced copy of $G$. While the problem of recognizing
balanceable graphs was conjectured to be NP-complete by Dailly, Hansberg, and
Ventura in 2021, balanceable graphs admit an elegant combinatorial
characterization: a graph is balanceable if and only there exist two vertex
subsets, one containing half of all the graph’s edges and another one such
that the corresponding cut contains half of all the graph’s edges. We consider
a special case of this property, namely when one of the two sets is a vertex
cover, and call the corresponding graphs simply balanceable. We prove a number
of results on balanceable and simply balanceable regular graphs. First, we
characterize simply balanceable regular graphs via a condition involving the
independence number of the graph. Second, we address a question of Dailly,
Hansberg, and Ventura from 2021 and show that every cubic graph is
balanceable. Third, using Brooks’ theorem, we show that every $4$-regular
graph with order divisible by $4$ is balanceable. Finally, we show that it is
NP-complete to determine if a $9$-regular graph is simply balanceable.

Keywords: balanceable graph, simply balanceable graph, cubic graph,
$4$-regular graph, regular graph, independent set

MSC (2020): 05C55, 05C75, 68Q25

##  1 Introduction

###  1.1 Background: balanceable graphs

A _$2$ -coloring_ of the edges of a complete graph $K_{n}$ is a function
$\varphi$ from the edge set of $K_{n}$ to the set $\\{R,B\\}$ of two colors,
red and blue. The well-known Ramsey’s theorem (see [11]) asserts that if $G$
is a complete graph, then any $2$-coloring of the edges of a large enough
complete graph $K_{n}$ yields a monochromatic copy of $G$. Caro et al. [5]
(see also [4]) considered a different approach to $2$-colorings of $K_{n}$,
asking for a _balanced copy_ of a graph $G$ in such a coloring and defined the
notion of _balanceability_.

A $2$-coloring $\varphi$ of the edges of $K_{n}$ is said to contain a balanced
copy of a graph $G$ if there exists a copy of $G$ in $K_{n}$ such that its
edge set $E$ can be partitioned in two parts $\left(E_{1},E_{2}\right)$ such
that $\left\|E_{1}|-|E_{2}\right\|\leq 1$ and $\varphi(e)=R$ for all $e\in
E_{1}$, and $\varphi(e)=B$ for all $e\in E_{2}$.

Let $G$ be a graph and $n$ be a positive integer. Let
bal$(n,G)<\lfloor\frac{1}{2}{n\choose 2}\rfloor$ be the smallest integer, if
it exists, such that every $2$-coloring $\varphi\colon
E\left(K_{n}\right)\rightarrow\\{R,B\\}$ of the edges of the complete graph
$K_{n}$ with $\left|\varphi^{-1}(R)\right|,\left|\varphi^{-1}(B)\right|>$
bal$(n,G)$ contains a balanced copy of $G$.111In [5], the condition
bal$(n,G)<\lfloor\frac{1}{2}{n\choose 2}\rfloor$ was not stated; however, this
condition is obviously necessary, since without it, bal$(n,G)$ would exist for
every $n$, for a trivial reason. If there exists an integer $n_{0}$ such that,
for every integer $n\geq n_{0}$, bal$(n,G)$ exists, then $G$ is said to be
_balanceable_.

It seems challenging to decide whether a graph is balanceable. Caro, Hansberg,
and Montejano [5] gave a characterization of balanceable graphs (see Section
1.2) and used it to show that all trees are balanceable. They also introduced
a new family of balanceable graphs called amoebas and developed their study
further in [6]. In an earlier work [4], the same authors showed that $K_{4}$
is the only balanceable complete graph with an even number of edges. In [9],
Dailly, Hansberg, and Ventura gave some conditions for a graph to be
balanceable and characterized the balanceability property within rectangular
and triangular grids, as well as for special circulant graphs. In general,
however, the question of which graphs are balanceable is widely open. In fact,
Dailly, Hansberg, and Ventura conjectured in [9] that the problem of
determining whether a given graph is balanceable is NP-complete. Further
interesting results on the notion of balanceability of graphs, variants, and
generalizations can be found in [3, 7, 8].

###  1.2 Simply balanceable graphs

Caro, Hansberg, and Montejano [5] gave a useful characterization of
balanceability. To state it, we need a couple of definitions. Given two
integers $k$ and $\ell$, we say that $\ell$ is _essentially half_ of $k$ if
$\ell\in\left\\{\left\lfloor\frac{k}{2}\right\rfloor,\left\lceil\frac{k}{2}\right\rceil\right\\}$.
The _size_ of a graph $G$ is the number of edges in $G$. Further, given a
graph $G=(V,E)$, we say that a set $X\subseteq V$ is an _internally balanced
set_ in $G$ if the number of edges with both endpoints in $X$ is essentially
half of the size of $G$. Similarly, $X$ is an _externally balanced set_ in $G$
if the number of edges with exactly one endpoint in $X$ is essentially half of
the size of $G$. In these terms, the announced characterization of
balanceability due to Caro, Hansberg, and Montejano (see [5, Theorem 2.6]) can
be stated as follows.

######  Theorem 1.1.

A graph $G$ is balanceable if and only if there exists an internally balanced
set in $G$ as well as an externally balanced set in $G$.

An interesting special case occurs if a graph $G$ admits an internally (or
externally) balanced set that is also a _vertex cover_ , that is, a set of
vertices touching all edges. Indeed, if $C$ is a vertex cover in $G$, then
every edge in $G$ has either both endpoints in $C$ or exactly one endpoint in
$C$. This immediately implies that the following conditions are equivalent:
(i) $C$ is internally balanced, (ii) $C$ is externally balanced, and (iii) the
complementary set $V\setminus C$ is externally balanced (the equivalence
between (ii) and (iii) holds for any set $C\subseteq V$). Furthermore, since a
set $X\subseteq V$ is a vertex cover if and only if $V\setminus X$ is an
independent set, the following conditions are equivalent for a graph $G$:

  1. (i)

there exists an internally balanced vertex cover in $G$,

  2. (ii)

there exists an externally balanced vertex cover in $G$, and

  3. (iii)

there exists an externally balanced independent set in $G$.

We say that a graph is _simply balanceable_ if it satisfies one of the above
three equivalent conditions (and, hence, all of them). The equivalence of
these three conditions and Theorem 1.1 imply that every simply balanceable
graph is balanceable, which justifies the choice of the name.

Many arguments establishing balanceability of certain graphs (see, e.g.,
Dailly, Hansberg, and Ventura [9]) are based on showing the existence of an
externally balanced independent set, that is, on showing that the graph is in
fact simply balanceable.

###  1.3 Our results

In this paper we continue the study of balanceable and simply balanceable
graphs, with a focus on regular graphs. We prove four main results.

Our first main result is the following characterization of simply balanceable
regular graphs via a condition involving the independence number of the graph.

######  Theorem 3.2.

Let $k\geq 2$ be an integer and let $G$ be an $n$-vertex $k$-regular graph.
Then $G$ is simply balanceable if and only if one of the following conditions
holds.

  1. 1.

$n\not\equiv 2~{}({\rm mod}~{}4)$ and $k=2$.

  2. 2.

$n\equiv 0~{}({\rm mod}~{}4)$ and $\alpha(G)\geq n/4$,

Theorem 3.2 has several consequences. First, it shows that in the case of
$2$-regular graphs, the balanceability and simple balanceability conditions
are equivalent. Second, it implies that if $G$ is a cubic graph of order $n$,
then $G$ is simply balanceable if and only if $n\equiv 0~{}({\rm mod}~{}4)$.
Furthermore, combined with Brooks’ theorem, it leads to the same
characterization of simple balanceability for connected $4$-regular graphs.

In contrast to the challenging question on recognizing balanceable graphs, our
second main result answers the analogous question for simply balanceable
graphs. The proof of this result is facilitated by Theorem 3.2.

######  Theorem 4.2.

Determining whether a given $9$-regular graph is simply balanceable is NP-
complete.

Next, we address a question of Dailly, Hansberg, and Ventura regarding
balanceability of cubic graphs (see [9]).

######  Theorem 5.1.

Every cubic graph is balanceable.

Finally, we turn our attention to the case of $4$-regular graphs. In this
case, a necessary condition for balanceability is that the graph has even
order. In the case of order $n\equiv 2~{}({\rm mod}~{}4)$, some graphs are
balanceable and some are not (see [9]). In contrast to this, we show, using
Brooks’ theorem, that there are no exceptions to balanceability in the case of
order $n\equiv 0~{}({\rm mod}~{}4)$.

######  Theorem 6.5.

Every $4$-regular graph of order $n$, where $n\equiv 0~{}({\rm mod}~{}4)$, is
balanceable.

Theorem 6.5 generalizes Lemmas 15 and 16 in [9], which establish that certain
$4$-regular circulant graphs are balanceable.

#### Structure of the paper.

After collecting the necessary preliminaries in Section 2, we characterize
simply balanceable regular graphs (Theorem 3.2) and derive several corollaries
in Section 3. We prove the NP-completeness result (Theorem 4.2) in Section 4.
Questions regarding balanceability of cubic and $4$-regular graphs are
investigated in Sections 5 and 6, respectively. We conclude the paper in
Section 7 with a summary of our results and some open questions.

##  2 Preliminaries

Throughout this paper, all graphs are assumed to be finite, simple (that is,
without loops or multiple edges), and undirected. The vertex and the edge set
of a graph $G$ are denoted with $V(G)$ and $E(G)$, respectively. The _order_
of $G$ is the number of vertices. For a vertex $v\in V(G)$, we denote by
$N_{G}(v)$ the set of all neighbors of $v$ and by $d_{G}(v)$ (or simply by
$d(v)$ if the graph is clear from the context) its degree. For a set
$X\subseteq V(G)$, we denote by $N(X)$ the set of vertices in $V(G)\setminus
X$ that have a neighbor in $X$ and by $N[X]$ the set $N(X)\cup X$. The maximum
degree of a vertex in $G$ is denoted by $\Delta(G)$. For a nonnegative integer
$k$, a graph is said to be _$k$ -regular_ if all its vertices have degree $k$.
We will refer to $3$-regular graphs also as _cubic_ graphs. A graph is
_regular_ if it is $k$-regular for some $k\geq 0$.

Let $G=(V,E)$ be a graph. A _vertex cover_ in $G$ is a set $C\subseteq V$ such
that every edge of $G$ has an endpoint in $C$. An _independent set_ in $G$ is
a set of pairwise nonadjacent vertices. We denote by $\alpha(G)$ be the
_independence number_ of $G$, that is, the maximum cardinality of an
independent set in $G$, and by $\chi(G)$ its _chromatic number_ , that is, the
smallest integer $k$ such that $G$ is $k$-colorable (that is, it admits a
partition of the vertex set into $k$ independent sets). Coloring greedily
vertices of a graph one at a time shows that every graph $G$ satisfies
$\chi(G)\leq\Delta(G)+1$. Furthermore, Brooks’ theorem [2] asserts that every
connected graph $G$ that is neither an odd cycle nor a complete graph is
$\Delta(G)$-colorable.

A _matching_ in a graph is a set of pairwise disjoint edges. A graph $G$ is
_$k$ -edge-colorable_ if it admits a partition of the edge set into $k$
matchings. The _chromatic index_ of $G$, denoted $\chi^{\prime}(G)$, is the
smallest integer $k$ such that $G$ is $k$-edge-colorable. The _line graph_ of
a graph $G=(V,E)$ is the graph $L(G)$ with vertex set $E$ in which distinct
two vertices are adjacent if and only if the corresponding edges of $G$ share
an endpoint.

The _Cartesian product_ of two graphs $G$ and $H$ is the graph $G\Box H$ with
vertex set $V(G\Box H)=V(G)\times V(H)$, and for which $(x,u)(y,v)$ is an edge
if and only if either $x=y$ and $uv\in E(H)$, or $xy\in E(G)$ and $u=v$. We
denote by $G+H$ the disjoint union of graphs $G$ and $H$. For a graph $G$ and
a set $X\subseteq V(G)$, we denote by $G[X]$ the subgraph of $G$ induced by
$X$, that is, the graph with vertex set $X$ in which two vertices are adjacent
if and only if they are adjacent in $G$. By $G-X$ we denote the subgraph of
$G$ induced by $V(G)\setminus X$.

Next, we recall the original formulation of the characterization of
balanceability given by Theorem 1.1. For a graph $G$ and a set $X\subseteq
V(G)$, we denote by $e_{G}(X)$ the number of edges in the subgraph of $G$
induced by $X$, and, for $Y\subseteq V(G)\setminus X$, by $e_{G}(X,Y)$ the
number of edges with one endpoint in $X$ and the other in $Y$.

######  Theorem 2.1 (A reformulation of Theorem 1.1).

A graph $G=(V,E)$ is balanceable if and only if $G$ has both a set of vertices
$W\subseteq V$ and a partition $V=\\{X,Y\\}$ such that

$e_{G}(W),\,e_{G}(X,Y)\in\left\\{\left\lfloor\frac{|E|}{2}\right\rfloor,\left\lceil\frac{|E|}{2}\right\rceil\right\\}\,.$
(1)

An interesting special case arises when the conditions from Theorem 2.1 are
satisfied with $W=X$. In particular, this is the case if $W$ is a vertex cover
in $G$ such that

$\left\lfloor\frac{|E|}{2}\right\rfloor\leq
e_{G}(W)\leq\left\lceil\frac{|E|}{2}\right\rceil\,.$

Indeed, in this case, setting $Y=V(G)\setminus W$ we have $e_{G}(Y)=0$ and
hence $|E|=e_{G}(W)+e_{G}(X,Y)$, implying (1). Reformulating the condition on
$W$ in terms of its complement $V(G)\setminus W$, which is an independent set,
leads to the following definition.

######  Definition 2.2.

A graph $G=(V,E)$ is _simply balanceable_ if there exists an independent set
$I$ in $G$ such that

$\left\lfloor\frac{|E|}{2}\right\rfloor\leq\sum_{x\in
I}d(x)\leq\left\lceil\frac{|E|}{2}\right\rceil\,.$

Note that, in terms of the terminology used in Section 1.2, a graph $G$ is
defined to be simply balanceable if there exists an externally balanced
independent set in $G$.

######  Proposition 2.3.

Every simply balanceable graph is balanceable.

[Proof]Let $G=(V,E)$ be simply balanceable and let $I$ be an independent set
$I$ in $G$ such that $\left\lfloor\frac{|E|}{2}\right\rfloor\leq\sum_{x\in
I}d(x)\leq\left\lceil\frac{|E|}{2}\right\rceil$. Then, condition (1) from
Theorem 2.1 is satisfied by the set $W=V\setminus I$ and the partition
$\\{X,Y\\}$ of $V$ given by $X=I$ and $Y=V\setminus I$ and, hence, $G$ is
balanceable.

Proposition 2.3 for even $|E|$ was extensively used in Dailly, Hansberg, and
Ventura [9], especially for graphs with an even number of edges. In
particular, for bipartite regular graphs, Proposition 2.3 implies the
following (see [9, Proposition 10]).

######  Proposition 2.4.

Every regular bipartite graph of order $n\equiv 0~{}({\rm mod}~{}4)$ is simply
balanceable.

It is not difficult to construct examples showing that the class of
balanceable graphs is not closed under disjoint union (see Remark 3.4).
Nevertheless, such a closure property holds under an additional assumption.

######  Lemma 2.5.

Let $G$ and $H$ be balanceable graphs such that $|E(H)|$ is even. Then $G+H$
is balanceable.

[Proof]Assume that $2k\leq|E(G)|\leq 2k+1$ and $|E(H)|=2\ell$ and for two
integers $k$ and $\ell$. Since $G$ is balanceable, by Theorem 2.1, there exist
subsets $W$ and $X$ of $V(G)$ such that $\ell\leq e_{G}(W)\leq\ell+1$ and
$\ell\leq e_{G}(X,V(G)\setminus X)\leq\ell+1$. Similarly, there are subsets
$Z$ and $Y$ of $V(H)$ such that $e_{H}(W)=e_{H}(Y,V(H)\setminus Y)=k$. Set
$U=W\cup Z$ and $S=X\cup Y$. Then

$e_{G+H}(U)=e_{G}(W)+e_{H}(Z)\in\\{k+\ell,k+\ell+1\\}$

and, similarly,

$e_{G+H}(S,V(G+H)\setminus S)=e_{G}(X,V(G)\setminus X)+e_{H}(Y,V(H)\setminus
Y)\in\\{k+\ell,k+\ell+1\\}\,.$

Since $2\ell+2k\leq|E(G+H)|\leq 2\ell+2k+1$, it follows that

$e_{G+H}(U),\,e_{G+H}(S,V(G+H)\setminus
S)\in\left\\{\left\lfloor\frac{|E(H+G)|}{2}\right\rfloor,\left\lceil\frac{|E(H+G)|}{2}\right\rceil\right\\}\,.$

Hence $G+H$ is balanceable by Theorem 2.1.

Let us say that a graph is _even_ if all its vertices have even degree. We
will make use of the following reformulation of [9, Proposition 7].

######  Proposition 2.6 (Dailly, Hansberg, and Ventura [9]).

Let $G=(V,E)$ be a balanceable even graph. Then $|E|$ is either odd or a
multiple of $4$.

##  3 A characterization of simply balanceable regular graphs

In this section, we address the question of which regular graphs are simply
balanceable. We first deal with the following easy special case.

######  Observation 3.1.

Every $1$-regular graph is simply balanceable.

[Proof]Let $G=(V,E)$ be a $1$-regular graph. Then, $G$ is a disjoint union of
$m$ edges, for some positive integer $m$, and any set of $\lceil{m/2}\rceil$
vertices, no two from the same edge, is an externally balanced independent
set, that is, an independent set $I$ satisfying the condition of Definition
2.2.

The remaining cases are characterized as follows.

######  Theorem 3.2.

Let $k\geq 2$ be an integer and let $G$ be an $n$-vertex $k$-regular graph.
Then $G$ is simply balanceable if and only if one of the following conditions
holds.

  1. 1.

$k=2$ and $n\not\equiv 2~{}({\rm mod}~{}4)$.

  2. 2.

$k\geq 3$, $n\equiv 0~{}({\rm mod}~{}4)$, and $\alpha(G)\geq n/4$.

[Proof]We first show that the conditions are sufficient. Assume first that
$k\geq 3$, $n\equiv 0~{}({\rm mod}~{}4)$, and $\alpha(G)\geq n/4$. Then, there
exists an independent set $I$ in $G$ such that $|I|=n/4$. Note that $|E|=kn/2$
and, hence, $\sum_{x\in I}d(x)=k|I|=kn/4=|E|/2$. Therefore, $G$ is simply
balanceable.

Assume now that $k=2$ and $n\not\equiv 2~{}({\rm mod}~{}4)$. Since $G$ is
$2$-regular, we have $|E|=n$. Furthermore, $G$ is $3$-colorable and hence
$\alpha(G)\geq n/3$. We consider three cases.

#### Case 1.

$n\equiv 0~{}({\rm mod}~{}4)$. Since $\alpha(G)\geq n/3\geq n/4$, we infer
that $G$ is simply balanceable by the above observation.

#### Case 2.

$n\equiv 1~{}({\rm mod}~{}4)$. Let $p$ be the positive integer such that
$n=4p+1$. Then $|E|=4p+1$. Since $\alpha(G)\geq n/3=(4p+1)/3\geq p$, there
exists an independent set $I$ in $G$ of size $p$. The sum of the degrees of
vertices in $I$ is

$\sum_{x\in I}d(x)=2|I|=2p=\left\lfloor\frac{|E|}{2}\right\rfloor\,.$

Hence, $G$ is simply balanceable.

#### Case 3.

$n\equiv 3~{}({\rm mod}~{}4)$. Let $p$ be the positive integer such that
$n=4p+3$. Then $|E|=4p+3$. Similarly as before, $\alpha(G)\geq
n/3=(4p+3)/3\geq p+1$; in particular, $G$ contains an independent set $I$ of
size $p+1$. The sum of the degrees of vertices in $I$ is

$\sum_{x\in I}d(x)=2|I|=2p+2=\left\lceil\frac{|E|}{2}\right\rceil\,.$

Hence, $G$ is simply balanceable.

Next, we show that the conditions are necessary. Assume that $G=(V,E)$ is
simply balanceable and let $I$ be an independent set in $G$ such that

$\left\lfloor\frac{|E|}{2}\right\rfloor\leq\sum_{x\in
I}d(x)\leq\left\lceil\frac{|E|}{2}\right\rceil\,.$

Since $\sum_{x\in I}d(x)=k|I|$ and $|E|=kn/2$, the above condition simplifies
to

$\left\lfloor\frac{kn}{4}\right\rfloor\leq
k|I|\leq\left\lceil\frac{kn}{4}\right\rceil\,.$

Suppose first that $|E|$ is even. Then $kn/4=|E|/2$ is an integer, implying
that $k|I|=kn/4$ and, hence, that $\alpha(G)\geq|I|=n/4$ and $n\equiv
0~{}({\rm mod}~{}4)$. In both cases, when either $k=2$ or $k\geq 3$, the
corresponding condition from the theorem statement is satisfied. We may thus
assume that $|E|$ is odd. Then $|E|/2=kn/4$ is an integer multiple of $1/2$
and

$kn/4-1/2\leq\left\lfloor\frac{kn}{4}\right\rfloor\leq
k|I|\leq\left\lceil\frac{kn}{4}\right\rceil\leq kn/4+1/2\,.$

Let $p=\left\lfloor\frac{n}{4}\right\rfloor$ and $q=n-4p$. Then
$q\in\\{1,2,3\\}$ and

$n/4-1/(2k)\leq|I|\leq n/4+1/(2k)\,.$

Using $n/4=p+q/4$, we obtain

$q/4-1/(2k)\leq|I|-p\leq q/4+1/(2k)\,.$ (2)

Assume that $k$ is odd. Then $n$ is even and thus $q=2$, and the chain of
inequalities (2) simplifies to

$1/2-1/(2k)\leq|I|-p\leq 1/2+1/(2k)\,,$

which together with $k\geq 3$ implies $1/3\leq|I|-p\leq 2/3$, a contradiction,
since $|I|-p$ is an integer. Thus, $k$ is even. Since $|E|=kn/2$ is odd, this
implies that $n$ is odd, that is, $q\in\\{1,3\\}$. If $q=1$, then (2) implies

$0\leq 1/4-1/(2k)\leq|I|-p\leq 1/4+1/(2k)\leq 1/2\,.$

Since $|I|-p$ is an integer, this is only possible if $|I|=p$ and $k=2$. Thus,
$G$ is $2$-regular and since $n$ is odd, $n\not\equiv 2~{}({\rm mod}~{}4)$.

Finally, if $q=3$, then (2) implies

$1/2\leq 3/4-1/(2k)\leq|I|-p\leq 3/4+1/(2k)\leq 1\,.$

Since $|I|-p$ is an integer, this is only possible if $|I|=p+1$ and $k=2$.
Thus, $G$ is $2$-regular and since $n$ is odd, $n\not\equiv 2~{}({\rm
mod}~{}4)$.

We now summarize the main consequences of Theorem 3.2 for simple
balanceability of $k$-regular graphs for $k\leq 4$. Dailly, Hansberg, and
Ventura [9] showed that for even $n\geq 4$, the $n$-vertex cycle is
balanceable if and only if $n\equiv 0~{}({\rm mod}~{}4)$. Using Theorem 3.2,
this result can be generalized as follows.

######  Corollary 3.3.

Let $G$ be a $2$-regular graph of order $n$. Then, the following statements
are equivalent.

  1. 1.

$G$ is balanceable.

  2. 2.

$G$ is simply balanceable.

  3. 3.

$n\not\equiv 2~{}({\rm mod}~{}4)$.

[Proof]Let $G=(V,E)$ be a $2$-regular graph and let $n$ be the order of $G$.
Since $G$ is $2$-regular, we have $2|V|=\sum_{x\in V}d(x)=2|E|$ and hence
$|E|=n$. If $G$ is balanceable, then, by Proposition 2.6, $n=|E|$ is either
odd or a multiple of $4$, that is, $n\not\equiv 2~{}({\rm mod}~{}4)$. If
$n\not\equiv 2~{}({\rm mod}~{}4)$, then $G$ is simply balanceable by Theorem
3.2. Finally, if $G$ is simply balanceable, then $G$ is balanceable by
Proposition 2.3.

######  Remark 3.4.

Corollary 3.3 shows, in particular, that the classes of balanceable and simply
balanceable graphs are not closed under disjoint union: the cycle $C_{3}$ is
simply balanceable, while the disjoint union of two copies of $C_{3}$ is not
balanceable. Similarly, a graph may be balanceable (or even simply
balanceable) even if none of its components are balanceable. This is the case
for the graph consisting of the disjoint union of two copies of $C_{6}$.
$\blacktriangle$

######  Corollary 3.5.

Let $G$ be a cubic graph of order $n$. Then $G$ is simply balanceable if and
only if $n\equiv 0~{}({\rm mod}~{}4)$.

[Proof]Let $G=(V,E)$ be a cubic graph of order $n$. By Theorem 3.2, it
suffices to show that $\alpha(G)\geq n/4$. But this follows from the fact that
$\chi(G)\leq\Delta(G)+1\leq 4$.

######  Corollary 3.6.

Let $G$ be a connected $4$-regular graph of order $n$. Then $G$ is simply
balanceable if and only if $n\equiv 0~{}({\rm mod}~{}4)$.

[Proof]Let $G=(V,E)$ be a connected $4$-regular graph of order $n$. By Theorem
3.2, it suffices to show that $\alpha(G)\geq n/4$. Since $K_{5}$ is the only
$4$-regular complete graph, $G$ is not complete. Since $G$ is also not an odd
cycle, Brooks’ theorem implies that $\chi(G)\leq 4$ and hence, the
independence number $\alpha(G)$ is at least $n/4$.

Note that the connectedness assumption in Corollary 3.6 is necessary. For
example, let $G$ be the graph consisting of the disjoint union of four
complete graphs $K_{5}$. Then, $G$ is a $4$-regular graph of order $n=20$.
Even though $n\equiv 0~{}({\rm mod}~{}4)$, we infer using Theorem 3.2 that $G$
is not simply balanceable, since the independence number of $G$ satisfies
$\alpha(G)=4<n/4$.

The above examples indicate that when studying balanceability and simple
balanceability of graphs in a certain class, extending the result from the
connected case to the general case may not always be straightforward. While
the extension was simple in the case of $2$-regular graphs and—as we will see
in Section 5—is also simple in the $3$-regular case, the $4$-regular case
turns out to be significantly more involved (see, e.g., the proof of Theorem
6.5).

The connection between simple balanceability of regular graphs and their
independence numbers established in Theorem 3.2 suggests that the problem of
recognizing simply balanceable graphs might be NP-complete. Before returning
to the study of balanceable graphs, we prove in the next section that this is
indeed the case.

##  4 Recognizing simply balanceable graphs is NP-complete

Our NP-completeness proof is based on a reduction from the following problem,
proved NP-complete by Leven and Galil [10]: Given a $4$-regular graph $G$, is
$G$ $4$-edge-colorable?

We will also use the following well-known fact relating $p$-colorability of a
graph with the independence number of the Cartesian product of the graph with
the complete graph $K_{p}$ (see, e.g., [1, p. 380]).

######  Proposition 4.1.

For any $n$-vertex graph $H$ and positive integer $p$, the graph $H$ is
$p$-colorable if and only if $\alpha(H\Box K_{p})=n$.

######  Theorem 4.2.

Determining whether a given $9$-regular graph is simply balanceable is NP-
complete.

[Proof]Clearly, the problem belongs to NP. Given an independent set $I$
satisfying the condition from the definition of simply balanceable graphs, it
can be verified in polynomial time whether $I$ is indeed an independent set
satisfying the condition.

To show NP-hardness, we make a reduction from the problem of $4$-edge-coloring
$4$-regular graphs. Given a $4$-regular graph $G$, compute the line graph
$L(G)$ and let $G^{\prime}$ be the Cartesian product of $L(G)$ with the
complete graph $K_{4}$. In other words, take four copies of $L(G)$, take their
disjoint union, and for each vertex of $L(G)$, add edges between any two
copies of the vertex. Since each edge of $G$ shares an endpoint with precisely
$6$ other edges, the line graph of $G$ is $6$-regular. Consequently, each
vertex of $G^{\prime}$ is adjacent to $6$ other vertices in the corresponding
copy of $L(G)$ and to $3$ other copies of the vertex in $G^{\prime}$, making
$G^{\prime}$ a $9$-regular graph. Let us denote by $m$ the number of edges of
$G$. Since the vertex set of $G^{\prime}$ is partitioned into $|V(L(G))|=m$
many $4$-cliques, the independence number of $G^{\prime}$ is at most $m$.
Furthermore, the number of vertices of $G^{\prime}$ is equal to $4m$; in
particular, $|V(G^{\prime})|\equiv 0~{}({\rm mod}~{}4)$. By Theorem 3.2,
$G^{\prime}$ is simply balanceable if and only if $\alpha(G^{\prime})\geq m$.

To complete the proof, we show that $G$ is $4$-edge-colorable if and only if
$\alpha(G^{\prime})\geq m$. Note first that $G$ is $4$-edge-colorable if and
only if $L(G)$ is $4$-colorable. Since $G^{\prime}=L(G)\Box K_{4}$, it follows
from Proposition 4.1 that $L(G)$ is $4$-colorable if and only if
$\alpha(G^{\prime})=|V(L(G))|=m$. As we already observed that
$\alpha(G^{\prime})\leq m$, we conclude that $G$ is $4$-edge-colorable if and
only if $\alpha(G^{\prime})\geq m$.

##  5 Balanceability of cubic graphs

As mentioned in the introduction, one of the aims of this paper is to study
the balanceability of cubic graphs, addressing a question of Dailly, Hansberg,
and Ventura [9]. The following theorem confirms that cubic graphs are
balanceable.

######  Theorem 5.1.

Every cubic graph is balanceable.

[Proof]Let $G=(V,E)$ be a cubic graph and let $n$ be the order of $G$. Since
$G$ is cubic, $n$ is even. We consider two cases depending on the value of
$n\bmod 4$.

#### Case 1.

$n\equiv 0~{}({\rm mod}~{}4)$. In this case, $G$ is balanceable by
Propositions 2.3 and 3.5.

#### Case 2:

$n\equiv 2~{}({\rm mod}~{}4)$. Let $k$ be the positive integer such that
$n=4k+2$. Then $|E|=6k+3$. Our goal is to show that the conditions of Theorem
2.1 are satisfied. In fact, we will show that $G$ has a set of vertices
$W\subseteq V$ and a partition $V=\\{X,Y\\}$ such that
$e_{G}(W)=e_{G}(X,Y)=3k+1$.

First, we show that there exists a partition $\\{X,Y\\}$ of $V$ such that
$e_{G}(X,Y)=3k+1$. We are going to construct $X$. Fix an arbitrary edge $xy\in
E$. Let $J=\\{x,y\\}$ and $H=G-N[J]$. Since the graph $G$ is cubic,
$|N[J]|\leq 6$ and hence, $|V(H)|\geq n-6$. As $H$ is a subgraph of $G$, we
have $\chi(H)\leq\chi(G)\leq 4$, which implies that
$\alpha(H)\geq|V(H)|/4\geq(n-6)/4=k-1$; in particular, there exists an
independent set $I$ in $H$ such that $|I|=k-1$. Let $X=I\cup J$ and
$Y=V\setminus X$; see Figure 1.

$x$$y$$\vdots$$X$$V\setminus X$$k-1$ Figure 1: Proof of Case 2 of Theorem 5.1
when $|N(\\{x,y\\})|=4$. The subgraph of $G$ induced by $X$ has a unique edge
$xy$ and $e_{G}(X,V\setminus X)=3k+1$.

Note that $xy$ is the unique edge of the subgraph of $G$ induced by $X$. Thus,
using also the fact that $G$ is cubic, we obtain that

$e_{G}(X,Y)=e_{G}(I,Y)+e_{G}(J,Y)=3(k-1)+4=3k+1\,,$

as claimed.

Second, to show that $G$ has a set of vertices $W\subseteq V$ such that
$e_{G}(W)=3k+1$, observe that the set $Y$ satisfies the desired condition.
Indeed,

$e_{G}(Y)=|E|-e_{G}(X)-e_{G}(X,Y)=(6k+3)-1-(3k+1)=3k+1\,.$

Applying Theorem 2.1, this completes the proof that $G$ is balanceable.

##  6 Balanceability of $4$-regular graphs

Proposition 2.6 implies the following.

######  Corollary 6.1.

No $4$-regular graph of odd order is balanceable.

[Proof]Let $G=(V,E)$ be a $4$-regular graph. Then $4|V|=2|E|$ and hence,
$|V|=|E|/2$; in particular, $|E|$ is even. By Proposition 2.6, $|E|$ is a
multiple of $4$. Consequently $|V|$ is even.

By Corollary 6.1, a necessary condition for the balanceability of a
$4$-regular graph is that it has even order. In the case of connected
$4$-regular graphs of order $n\equiv 2~{}({\rm mod}~{}4)$, some graphs are
balanceable and some are not (see [9]). However, we next show that in the case
$n\equiv 0~{}({\rm mod}~{}4)$ they are all balanceable. Note that Propositions
2.3 and 3.6 imply the following.

######  Lemma 6.2.

Every connected $4$-regular graph of order $n$, where $n\equiv 0~{}({\rm
mod}~{}4)$, is balanceable.

For the general case, we will make use of the following consequence of Lemma
2.5.

######  Corollary 6.3.

Let $G$ and $H$ be balanceable graphs such that $H$ is $4$-regular. Then $G+H$
is balanceable.

We will also need the following sufficient condition for balanceability of
$4$-regular graphs.

######  Lemma 6.4.

Every $4$-colorable $4$-regular graph of order $n$, where $n\equiv 0~{}({\rm
mod}~{}4)$, is balanceable.

We omit the proof of Lemma 6.4, since it is the same as the proof of Corollary
3.5.

######  Theorem 6.5.

Every $4$-regular graph of order $n$, where $n\equiv 0~{}({\rm mod}~{}4)$, is
balanceable.

[Proof]Suppose for a contradiction that there exists a $4$-regular graph of
order $n$ divisible by $4$ that is not balanceable, and let $G$ be a
counterexample minimizing $n$. By Lemma 6.2, $G$ is disconnected. In the
proof, we will analyze the structure of components of $G$, eventually reaching
a contradiction. Let $\mathcal{K}$ be the set of components of $G$ that are
complete graphs (that is, isomorphic to $K_{5}$), let $U$ be the set of
vertices belonging to a component in $\mathcal{K}$, and let $a$ be the
cardinality of $\mathcal{K}$. Furthermore, for $i\in\\{0,1,2,3\\}$, let
$a_{i}$ be the number of components $C$ of $G-U$ such that and $|V(C)|\equiv
i~{}({\rm mod}~{}4)$.

We continue the proof by proving several claims.

######  Claim 1.

Let $\mathcal{C}$ be a nonempty proper subset of the set of components of $G$
and let $S$ by the set of vertices of $G$ that belong to a component in
$\mathcal{C}$. Then $|S|\not\equiv 0~{}({\rm mod}~{}4)$.

[Proof]Suppose that $|S|\equiv 0~{}({\rm mod}~{}4)$. The assumption on
$\mathcal{C}$ implies that the set $S$ is a nonempty proper subset of $V(G)$.
The subgraphs of $G$ induced by $S$ and $V(G)\setminus S$ are $4$-regular and
of order divisible by $4$, hence, by the minimality of $G$, they are both
balanceable. By Corollary 6.3, $G$ is balanceable, a contradiction.

######  Claim 2.

$a_{0}=0$.

[Proof]Suppose that $a_{0}>0$. Then, there exists a component $C$ of $G$ such
that $|V(C)|\equiv 0\pmod{4}$. Since $G$ is disconnected, the set $\\{C\\}$ is
a nonempty proper subset of the set of components of $G$. Hence,
$|V(C)|\not\equiv 0\pmod{4}$ by 1, a contradiction.

######  Claim 3.

$a\in\\{1,2,3\\}$.

[Proof]If $a=0$, then by Brooks’ theorem, $G$ is $4$-colorable and, hence,
balanceable by Lemma 6.4, a contradiction. Therefore, $a\geq 1$. Suppose for a
contradiction that $a\geq 4$. Choose a set $\mathcal{C}$ of any $4$ components
from $\mathcal{K}$ and let $S$ by the set of vertices of $G$ that belong to a
component in $\mathcal{C}$. If $S\neq V(G)$, then 1 implies that
$|S|\not\equiv 0~{}({\rm mod}~{}4)$, a contradiction. Hence, $S=V(G)$. In
particular, $\mathcal{C}=\mathcal{K}$ and $G$ is the disjoint union of four
copies of $K_{5}$. Choose any two components of $G$, let $V_{1}$ and $V_{2}$
denote their vertex sets, and let $H$ be the subgraph of $G$ induced by
$V_{1}\cup V_{2}$. Fix an arbitrary vertex $v_{1}\in V_{1}$ and two distinct
vertices $v_{2},v_{2}^{\prime}\in V_{2}$. Then $H$ is balanceable, as verified
by applying Theorem 2.1 to the set $W=V_{1}$ and the partition $\\{X,Y\\}$ of
$V(G)$ given by $X=\\{v_{1},v_{2},v_{2}^{\prime}\\}$ and $Y=V(H)\setminus X$.
Note that $G$ is isomorphic to the disjoint union of two copies of $H$. Since
$|E(H)|=20$, Lemma 2.5 implies that $G$ is balanceable, a contradiction.
Therefore, $a\leq 3$ and we conclude that $a\in\\{1,2,3\\}$, as claimed.

######  Claim 4.

$a_{3}=0$.

[Proof]Suppose that $a_{3}>0$. Let $H$ be a component of $G$ such that
$|V(H)|=4k+3$ for some integer $k$. By 3, $G$ has a component $K$ that is
isomorphic to $K_{5}$. Note that $|V(K+H)|\equiv 0\pmod{4}$. If $V(K+H)\neq
V(G)$, then 1 implies that $|V(K+H)|\not\equiv 0\pmod{4}$, a contradiction.
Hence $G=K+H$. By Brooks’ theorem, $H$ has an independent set $I$ such that
$|I|=\left\lceil\frac{|V(H)|}{4}\right\rceil=k+1$. Let $J=I\cup\\{v\\}$, where
$v$ is an arbitrary vertex of $K$. Thus $J$ is an independent set of $G$ and

$\sum_{x\in J}d(x)=4|J|=4(k+2)=4k+8=|V(G)|=\frac{|E(G)|}{2}.$

So $G$ is balanceable by Proposition 2.3, a contradiction.

######  Claim 5.

$a\leq 1$ or $a_{2}=0$.

[Proof]Suppose that $a\geq 2$ and $a_{2}>0$. Let $H$ be an induced subgraph of
$G$ consisting of two components isomorphic to $K_{5}$ and let $H^{\prime}$ be
a component of $G$ with $|V(H^{\prime})|\equiv 2\pmod{4}$. Note that
$|V(H^{\prime}+H)|\equiv 0\pmod{4}$. If $V(H^{\prime}+H)\neq V(G)$, then 1
implies that $|V(H^{\prime}+H)|\not\equiv 0\pmod{4}$, a contradiction. Hence
$G=H+H^{\prime}$; in particular, $G$ is isomorphic to the disjoint union of
$H^{\prime}$ and two copies of $K_{5}$. We have $|V(H^{\prime})|=4k+2$ for
some integer $k$. Using Brooks’ theorem, we infer that $\chi(H^{\prime})\leq
4$. Thus, there exists an independent set $I^{\prime}$ in $H^{\prime}$ such
that $|I^{\prime}|=\left\lceil\frac{|V(H^{\prime})|}{4}\right\rceil=k+1$.
Choose two vertices $u$ and $v$ in different components of $H$ and set
$I=I^{\prime}\cup\\{u,v\\}$. Then $|I|=k+3$ and $|V(G)|=4k+2+10=4(k+3)=4|I|$.
So $\sum_{x\in I}d(x)=4|I|=|V(G)|=\frac{|E(G)|}{2}$. By Proposition 2.3, $G$
is balanceable, a contradiction.

######  Claim 6.

$a=1$ or $a_{2}=0$.

[Proof]Immediately from Claims 3 and 5.

######  Claim 7.

$a_{1}\leq 2$.

[Proof]Suppose that $a_{1}\geq 3$. Let $F$ be an induced subgraph of $G$
consisting of one component isomorphic to $K_{5}$ and three components
$C_{j}$, where $j\in\\{1,2,3\\}$, of $G-U$ of order $|V(C_{j})|=4k_{j}+1$ such
that $k_{j}$ is an integer. Since $|V(F)|\equiv 0\pmod{4}$, 1 implies that
$G=F$. By Brooks’ theorem, each component $C_{j}$ contains an independent set
$I_{j}$ of size $k_{j}+1$. Put $I=I_{1}\cup I_{2}\cup I_{3}\cup\\{v\\}$. Then

$\sum_{x\in I}d(x)=4|I|=4(k+2)=4k+8=|V(G)|=\frac{|E(G)|}{2}\,,$

hence, $G$ is balanceable by Proposition 2.3, a contradiction.

######  Claim 8.

$a_{2}>0$.

[Proof]Suppose, contrary to our claim, that $a_{2}=0$. Then according to
assumption of the theorem

$|V(G)|=\sum\\{|V(C)|\colon C\text{ is a component of}~{}G\\}$

should be $0$ modulo $4$. Using 4, this implies that $a+a_{1}\equiv
0\pmod{4}$. By 3, we have $a\in\\{1,2,3\\}$. Since $a+a_{1}\equiv 0\pmod{4}$,
we infer that $a_{1}\equiv c\pmod{4}$ where $c=4-a$.

Set $G^{\prime}=G-U$. Note that $c\in\\{1,2,3\\}$ and $G^{\prime}$ has at
least $c$ components. Choose a set $\mathcal{C}$ of $c$ components of
$G^{\prime}$ and let $F$ be the subgraph of $G$ induced by
$U\cup\bigcup_{C\in\mathcal{C}}V(C)$. Then $|V(F)|\equiv 0\pmod{4}$ and 1
implies that $G=F$. Choose an independent set $J\subseteq U$ containing one
vertex from each component in $\mathcal{K}$. For each component
$C\in\mathcal{C}$, we have $|V(C)|=4k_{C}+1$ for some integer $k_{C}$. Brooks’
theorem implies that each component $C\in\mathcal{C}$ has an independent set
$J_{C}$ of size $\left\lceil\frac{|V(C)|}{4}\right\rceil=k_{C}+1$. Fix a
component $D\in\mathcal{C}$. For each component
$C\in\mathcal{C}\setminus\\{D\\}$, set $I_{C}$ to be an arbitrary subset of
$J_{C}$ such that $|I_{C}|=k_{C}$, that is, $I_{C}$ is obtained from $J_{C}$
by deleting from it an arbitrary vertex. Set

$I=J\cup J_{D}\cup\bigcup_{C\in\mathcal{C}\setminus\\{D\\}}I_{C}.$

Then $I$ is an independent set in $G$ such that

$|I|=a+(k_{D}+1)+\sum_{C\in\mathcal{C}\setminus\\{D\\}}k_{C}=\sum_{C\in\mathcal{C}}k_{C}+a+1\,.$

Furthermore,

$|V(G)|=|V(F)|=5a+\sum_{C\in\mathcal{C}}(4k_{C}+1)=4\sum_{C\in\mathcal{C}}k_{C}+5a+c=4\sum_{C\in\mathcal{C}}k_{C}+4a+4\,.$

Therefore,

$\sum_{x\in
I}d(x)=4|I|=4\sum_{C\in\mathcal{C}}k_{C}+4a+4=|V(G)|=\frac{|E(G)|}{2}\,,$

hence, $G$ is balanceable by Theorem 2.1, a contradiction.

######  Claim 9.

$a=1$.

[Proof]Immediately from Claims 6 and 8.

######  Claim 10.

$a_{1}=1$.

[Proof]Suppose for a contradiction that $a_{1}\neq 1$. Then 7 implies that
$a_{1}\in\\{0,2\\}$. Using Claims 4 and 9, we infer that $|V(G)|\equiv
a_{1}+1\pmod{4}$. Hence, $|V(G)|$ is odd, a contradiction.

Now we are ready to complete the proof of Theorem 6.5. Let $F$ be an induced
subgraph of $G$ consisting of the unique component of $G$ isomorphic to
$K_{5}$, the unique component $C$ of $G-U$ with $|V(C)|=4k+1$ for some integer
$k$, and exactly one component $C^{\prime}$ with
$|V(C^{\prime})|=4k^{\prime}+2$ for some integer $k^{\prime}$. Since
$|V(F)|\equiv 0\pmod{4}$, 1 implies that $G=F$. Using Brooks’ theorem, we can
see that $C$ contains an independent set $I$ of size $k+1$ and $C^{\prime}$
has an independent set $I^{\prime}$ of size $k^{\prime}+1$. Set $J=I\cup
I^{\prime}$. Note that $|V(G)|=|V(F)|=4(k+k^{\prime})+8$, moreover
$|J|=k+k^{\prime}+2$ and hence $\sum_{x\in J}d(x)=|V(G)|=\frac{|E(G)|}{2}$. So
$G$ is balanceable due to Proposition 2.3, a contradiction. This completes the
proof.

As shown by the disjoint union of $4$ copies of the complete graph $K_{5}$
(see the paragraph after the proof of Corollary 3.6), Theorem 6.5 cannot be
strengthened by replacing balanceability with simple balanceability.

Theorem 6.5 generalizes Lemmas 15 and 16 in [9], which establish that certain
$4$-regular circulant graphs are balanceable. The theorem also implies the
following.

######  Corollary 6.6.

For every cubic graph $G$, the graph $G\Box K_{2}$ is balanceable.

[Proof]It can be easily seen that $G\Box K_{2}$ is a $4$-regular graph.
Furthermore, since $G$ is cubic, it has an even number of vertices. Hence
$n=|V(G\Box K_{2})|=|V(G)|\times|V(K_{2})|$ is even and $n\equiv 0~{}({\rm
mod}~{}4)$. By Theorem 6.5, $G\Box K_{2}$ is balanceable.

##  7 Conclusion

We proved several new results about regular balanceable graphs. Important
tools in our approach are Brooks’ theorem and a sufficient condition for
balanceability, which we call simple balanceability. We characterized simply
balanceable regular graphs via a condition involving the independence number
of the graph, leading, on the one hand, to polynomially recognizable cases for
small degrees and, on the other hand, to an NP-completeness proof for the
problem of recognizing simply balanceable $9$-regular graphs.

While balanceability coincides with simple balanceability for $k$-regular
graphs with $k\in\\{1,2\\}$, this is not the case for $k\in\\{3,4\\}$. For
these cases we obtained either complete (for $k=3$) or partial (for $k=4$)
characterizations of balanceability. In particular, the results of Sections 3
and 5 answer the question regarding the complexity of recognizing balanceable
graphs when the input is restricted to $k$-regular graphs for $k\leq 3$. For
all $k\geq 4$, the question remains open.

Our results are summarized in Tables 1 and 2.

$k$ | Characterizing conditions | Recognition complexity
---|---|---
$1$ | / (3.1) |  P (trivial)
$2$ |  $n\not\equiv 2~{}({\rm mod}~{}4)$ (Corollary 3.3) |  P (Corollary 3.3)
$3$ | / (Theorem 5.1) |  P (trivial)
$4$ | ? ($n\equiv 0~{}({\rm mod}~{}2)$ is necessary by Corollary 6.1, | ? (in P if $n\not\equiv 2~{}({\rm mod}~{}4)$,
|  $n\equiv 0~{}({\rm mod}~{}4)$ is sufficient, by Theorem 6.5) | by Corollaries 6.1 and 6.5)
$\geq 5$ | ? | ?
Table 1: Summary of our results on balanceability of $k$-regular graphs of
order $n$, for various small values of $k$. NPc stands for “NP-complete”, P
for “solvable in polynomial time”. Question marks denote open questions.

$k$ Characterizing conditions Recognition complexity $1$ / (3.1) P (trivial)
$2$ $n\not\equiv 2~{}({\rm mod}~{}4)$ (Corollary 3.3) P (Corollary 3.3) $3$
$n\equiv 0~{}({\rm mod}~{}4)$ (Corollary 3.5) P (Corollary 3.5) $4$ $n\equiv
0~{}({\rm mod}~{}4)$ (if $G$ is connected) (Corollary 3.6) ? (in P if $G$ is
connected, by Corollary 3.6) $\geq 5$ $n\equiv 0~{}({\rm mod}~{}4)$ and
$\alpha(G)\geq n/4$ (LABEL:{lem:regular-sb}) NPc for $k=9$ (Proposition 4.1),
open for all other values of $k$

Table 2: Summary of our results on simple balanceability of $k$-regular graphs
of order $n$, for various small values of $k$. NPc stands for “NP-complete”, P
for “solvable in polynomial time”. The question mark denotes an open question.

Besides determining the complexity of recognizing balanceable graphs within
the classes of $k$-regular graphs for $k\geq 4$, or even in general (which
Dailly, Hansberg, and Ventura conjectured to be NP-complete [9]), it would be
interesting classify the boundary between easy and difficult cases for the
recognition of simply balanceable $k$-regular graphs. In particular, is there
an integer $k_{0}$ such that recognizing simply balanceable $k$-regular graphs
is polynomial-time solvable for all $k<k_{0}$ and NP-complete for all $k\geq
k_{0}$? The results of this paper imply that if such a $k_{0}$ exists, then
$4\leq k_{0}\leq 9$, unless $\textsf{P}=\textsf{NP}$. Understanding the
balanceability and simple balanceability properties within hereditary graph
classes (that is, graph classes closed under vertex deletion) is also a
largely unexplored topic, which we leave for future research.

### Acknowledgments

This work is supported in part by the Slovenian Research and Innovation Agency
(I0-0035, research program P1-0285 and research projects J1-3001, J1-3002,
J1-3003, J1-4008, J1-4084, N1-0160, and N1-0208), and by the research program
CogniCom (0013103) at the University of Primorska.

## References

  * [1] Claude Berge.  Graphs and hypergraphs, volume 6 of North-Holland Math. Libr. Elsevier (North-Holland), Amsterdam, 1973.
  * [2] R. Leonard Brooks.  On colouring the nodes of a network.  Proc. Cambridge Philos. Soc., 37:194–197, 1941.  doi:10.1017/S030500410002168X.
  * [3] Yair Caro, Adriana Hansberg, Josef Lauri, and Christina Zarb.  On zero-sum spanning trees and zero-sum connectivity.  Electron. J. Combin., 29(1):Paper No. 1.9, 24, 2022.  doi:10.37236/10289.
  * [4] Yair Caro, Adriana Hansberg, and Amanda Montejano.  Zero-sum $K_{m}$ over $\mathbb{Z}$ and the story of $K_{4}$.  Graphs Combin., 35(4):855–865, 2019.  doi:10.1007/s00373-019-02040-3.
  * [5] Yair Caro, Adriana Hansberg, and Amanda Montejano.  Unavoidable chromatic patterns in 2-colorings of the complete graph.  J. Graph Theory, 97(1):123–147, 2021.  doi:10.1002/jgt.22645.
  * [6] Yair Caro, Adriana Hansberg, and Amanda Montejano.  Graphs isomorphisms under edge-replacements and the family of amoebas.  Electron. J. Combin., 30(3):Paper No. 3.9, 38, 2023.  doi:10.37236/11876.
  * [7] Yair Caro, Josef Lauri, and Christina Zarb.  On small balanceable, strongly-balanceable and omnitonal graphs.  Discuss. Math. Graph Theory, 42(4):1219–1235, 2022.  doi:10.7151/dmgt.2342.
  * [8] Antoine Dailly, Laura Eslava, Adriana Hansberg, and Denae Ventura.  The balancing number and generalized balancing number of some graph classes.  Electron. J. Combin., 30(1):Paper No. 1.48, 22, 2023.  doi:10.37236/10032.
  * [9] Antoine Dailly, Adriana Hansberg, and Denae Ventura.  On the balanceability of some graph classes.  Discrete Appl. Math., 291:51–63, 2021.  doi:10.1016/j.dam.2020.12.005.
  * [10] Daniel Leven and Zvi Galil.  NP-completeness of finding the chromatic index of regular graphs.  J. Algorithms, 4:35–44, 1983.  doi:10.1016/0196-6774(83)90032-9.
  * [11] Frank P. Ramsey.  On a Problem of Formal Logic.  Proc. London Math. Soc. (2), 30(4):264–286, 1929.  doi:10.1112/plms/s2-30.1.264.