1. Graph labelings and colorings
An edge-magic total (EMT) labeling on a graph with v vertices and e edges will be defined as a one-to-one map taking the vertices and edges onto the integers {1,2,...,v+e} with the property that the sum of the label on an edge and the labels of its endpoints is constant independent of the choice of edge. A graph is called edge-magic total if it admits any edge-magic total labeling.For a simple connected graph $G = (V (G), E(G))$, a radio labeling is a mapping $f : V (G) \rightarrow \{0, 1, 2, . . .\}$ such that $|f(u)−f(v)| \ge diam(G)+1−d(u, v)$ for each pair of distinct vertices $u, v \in V (G)$, where $diam(G)$ is the diameter of $G$ and $d(u, v)$ is the distance between $u$ and $v$. A radio labeling $f$ of a graph $G$ is a radio graceful labeling of $G$ if $f(V (G)) = \{0, 1, . . . , |V (G)| − 1\}$. A graph for which a radio graceful labeling exists is called radio graceful.
-
EMT labeling of disjoint union of cycles
When $n$ is odd or $n \equiv 2 \mod 4$, it is known that the disjoint union $C_n \ \dot{\cup} \ C_n$ is edge-magic total.Problem 1.05.
[Bryan Freyberg] For even $n$, determine if the disjoint union $C_n \ \dot{\cup} \ C_n$ is edge-magic total. For $m \ge n$, determine if the disjoint union $C_m \ \dot{\cup} \ C_n$ is edge-magic total. -
Vertex distinguishing achromatic edge coloring
A proper edge coloring graph $G$ is called a vertex distinguishing edge coloring if for any two distinct vertices $u$ and $v$ of $G$, the set of the colors assigned to the edges incident to $u$ differs from the set of the colors assigned to the edges incident to $v$. The minimum number of colors required is often of interest. We instead investigate the maximum number of colors in a minimal coloring, in the sense that no color classes can be combined, that is a vertex distinguishing edge labeling .Conjecture 1.1.
[Anne Saiko] Let $n \ge 4$. The maximum number of colors in a minimal vertex distinguishing edge labeling is $\lfloor \frac{2n}{3}\rfloor +1 $. -
Radio graceful Cartesian graph products
The Cartesian product of radio graceful graphs is often radio graceful, but it is not necessary. We investigate sufficient conditions for this to hold, and consider if a radio graceful Cartesian product must have radio graceful factors.Problem 1.15.
[Amanda Niedzialomski] Determine conditions on graphs $G$ and $H$ that guarantee $G \ \square \ H$ is radio graceful. In the other direction, given $G \ \square \ H$ is radio graceful, determine if $G$ and $H$ are radio graceful.-
Remark. [Shanise Walker] It may also be of interest to consider a similar question for other graph operations like vertex deletion, edge deletion, or edge contraction. That is, determine conditions on a graph $G$ that guarantee $G$ under the graph operation is radio graceful.
-
-
EMT labeling for grid graphs
In "A Dynamic Survey of Graph Labeling", Gillian states edge magic total labelings for $P_m \ \square \ P_n$ are known to exist. The reference listed for this result is either mislabeled or requires further steps to show it is true.Problem 1.2.
[Bryan Freyberg] Let $m \ge n$. Determine the validity of the existence of edge total labelings for $P_m \ \square \ P_n$. Determine the existence of edge total labelings for $C_m \ \square \ P_n$. -
A linear algebra interpretation of labelings
Problem 1.25.
[Veronika Furst] Determine linear algebra properties that correspond to the existence of particular labelings. -
Variations on total labelings
We want to consider the graph labelings where edge labels are distinct and vertex labels are able to repeat, or vertex labels are distinct and edge labels are able to repeat.Problem 1.3.
[Zhanar Berikkyzy] Determine which graphs admit such a graph labeling. For such graphs, determine the minimum number of labels required. -
Fractional labeling
Graph labelings rely on integers to label the vertices and edges. Instead we want to expand the labeling set and allow labels to be in $\mathbb{Q}$.Problem 1.35.
[Aysel Erey] Determine graphs that admit such a fractional labeling. In particular, determine graphs that admit a fractional labeling but not an integer labeling. -
Random graph labeling
For a given graph labeling, we want to consider the probability that a random labeling satisfies the desired labeling conditions. We first consider radio labeling.Problem 1.4.
Given a graph $G$ with random vertex label, determine the probability that $G$ is radio labeled. -
Distance antimagic labeling
Given a graph $G$, we label the vertices with integers {1,2,...,|V(G)|} with the property that for distinct vertices $u$ and $v$ the sum of the labels on the neighbors of $u$ differs from the sum of labels on the neighbors of $v$. Thus it is necessary that every vertex to have a distinct neighborhood. We call such a labeling a distance version of antimagic labeling and a graph that admits such a labeling is distance antimagic. It is also conjectured that this condition is sufficient for such a labeling.Conjecture 1.45.
A graph is distance antimagic if and only if all the vertices have a distinct neighborhood.-
Remark. [Rinovia Simanjuntak] Considering the neighbors of each vertex is equivalent to considering the $d$-neighborhood where $d$ is the maximum distance between the vertices when $d=1$. We could also consider $d \ge 2$.
-
Remark. [Rinovia Simanjuntak] It is also of interest to consider when Cartesian products are distance anitmagic. For example, given $G$ is distance antimagic, determine if $G \ \square \ K_2$ is distance antimagic.
-
-
Distance magic labeling
Given a graph $G$, we label the vertices with integers $\{1,2,...,|V(G)|\}$ with the property that the sum of the labels on the neighbors of a vertex is constant. We call such a labeling a distance version of magic labeling and a graph that admits such a labeling is distance magic.Problem 1.5.
[Bryan Freyberg] Let $r$ be even and $n$ be odd. For a $r$-regular graph of order $n$, determine if such a labeling exists.-
Remark. This problem has applications to tournament scheduling. For $n$ even, results are known.
-
-
Neighborhood balanced coloring
A neighbor bounding coloring on a graph $G$ is a $(R,B)$-coloring on the vertices of $G$ such that for any vertex there exists an equal number of neighbors colored R and colored B. We consider a variation on this coloring, allowing the number of neighbors colored R and colored B to differ by at most 1.Problem 1.55.
[Alison Marr] Determine graphs that admit such a coloring.-
Remark. [Alison Marr] There are several variations on a neighborhood balanced coloring we could consider. Closed neighborhoods could be considered, as well as a similar neighborhood balanced coloring that concerns having at most $k$ colors evenly distributed over each neighborhood.
-
Cite this as: AimPL: Graph Theory: structural properties, labelings, and connections to applications, available at http://aimpl.org/graphstructureapp.