A graph $G$ with $k$ vertices is distance magic if the vertices can be labeled with numbers $1,2,\dots ,k$ so that the sum of labels of the neighbors of each vertex is equal to the same constant ${\mu }_0$. We present a construction of distance magic graphs arising from arbitrary regular graphs based on an application of magic rectangles. We also solve a problem posed by Shafig, Ali, and Simanjuntak.

Given a graph $G$, a function $f:V(G)\to \{1,2,\dots ,k\}$ is a $k$-ranking of $G$ if $f(u)=f(v)$ implies every $u$-$v$ path contains a vertex $w$ such that $f(w)>f(u)$. A $k$-ranking is \emph{minimal} if the reduction of any label greater than $1$ violates the described ranking property. The rank number of a graph, denoted ${\chi }_r(G)$, is the minimum $k$ such that $G$ has a minimal $k$-ranking. The arank number of a graph, denoted ${\psi }_r(G)$, is the maximum $k$ such that $G$ has a minimal $k$-ranking. It was asked by Laskar, Pillone, Eyabi, and Jacob if there is a family of graphs where minimal $k$-rankings exist for all ${\chi }_r(G)\le k\le {\psi }_r(G)$. We give an affirmative answer showing that all intermediate minimal $k$-rankings exist for paths and cycles. We also give a characterization of all complete multipartite graphs which have this intermediate ranking property and which do not.

Let $G$ be a $(p,q)$-graph where each edge of $G$ is labeled by a number $1,2,\dots ,q$ without repetition. The vertex sum for a vertex $v$ is the sum of the labels of edges that are incident to $v$. If the vertex sums are equal to a constant (mod $k$) where $k\ge 2$, then $G$ is said to be Mod($k$)-edge-magic. In this paper, we investigate graphs which are Mod($k$)-edge-magic. When $k=p$, the corresponding Mod($p$)-edge-magic graph is the edge-magic graph introduced by Lee (third author), Seah, and Tan in $[10]$. In this work, we investigate trees, unicyclic graphs, and $(p,p+1)$-graphs which are Mod(2)-edge-magic.

First posed in 1942 by Kelly and Ulam, the Graph Reconstruction Conjecture is one of the major open problems in graph theory. While the Graph Reconstruction Conjecture remains open, it has spawned a number of related questions. In the classical vertex graph reconstruction number problem, a vertex is deleted in every possible way from a graph $G$, and then it can be asked how many (both minimum and maximum) of these subgraphs are required to reconstruct $G$ up to isomorphism. This can then be extended to deleting $k$ vertices in every possible way.

Previous computer searches have found the 1-vertex-deletion reconstruction numbers of all graphs of up to 11 vertices. In this paper, computed values of $k$-vertex-deletion reconstruction numbers for all graphs on up to 8 vertices and $k\le |V(G)|–2$ are reported, as well as for some $k$ for graphs on 9 vertices. Our data suggested a number of new theorems and conjectures. In particular, we pose, as a generalization of the Graph Reconstruction Conjecture, that any graph on $3k$ or more vertices is $k$-vertex-deletion reconstructible.

Let $G$ be a simple graph with a vertex set $V(G)$ and an edge set $E(G)$, and let ${\mathbb{Z}}_2=\{0,1\}$. A labeling $f:V(G)\to {\mathbb{Z}}_2$ induces an edge partial labeling $f^{\ast }:E(G)\to {\mathbb{Z}}_2$ defined by $f^{\ast }(xy)=f(x)$ if and only if $f(x)=f(y)$ for each edge $xy\in E(G)$. For each $i\in {\mathbb{Z}}_2$, let $v_f(i)=|\{v\in V(G):f(v)=i\}|$ and $e_f(i)=|\{e\in E(G):f^{\ast }(e)=i\}|$. The balance index set of $G$, denoted $\text{BI}(G)$, is defined as $\{|e_f(0)–e_f(1)|:|v_f(0)–v_f(1)|\le 1\}$. In this paper, we investigate and present results concerning the balance index sets of trees of diameter four.

In this paper, we present new results about the coloring of graphs. We generalize the notion of proper vertex-coloring, introducing the concept of range-coloring of order $k$. The relation between range-coloring of order $k$ and total coloring is presented: we show that for any graph $G$ that has a range-coloring of order $\mathrm{\Delta }(G)$ with $t$ colors, there is a total coloring of $G$ that uses $(t+1)$ colors. This result provides a framework to prove that some families of graphs satisfy the total coloring conjecture. We exemplify with the family of block-cactus graphs.

We show, for $k=3,4,5$, that the necessary conditions are sufficient for the existence of graph designs which decompose $K_v(\lambda ,j)$, the complete (multi)graph on $v$ points with $\lambda$ multiple edges for each pair of points and $j$ loops at each vertex, into ordered blocks $(a_1,a_2,\dots ,a_{k-1},a_1)$. Each block is the subgraph which contains both the set of unordered edges $\{a_i,a_j\}$, for each pair of consecutive edges in the ordered list, and also the loop at vertex $a_1$.

We investigate the existence of fixed point families for the eccentric digraph ($\text{ED}$) operator, which was introduced in $[1]$. In $[2]$, the notion of the period $\rho (G)$ of a digraph $G$ (under the $\text{ED}$ operator) was defined, and it was observed, but not proved, that for any odd positive integer $m$, $C_m\times C_m$ is periodic, and that $\rho (\text{ED}(C_m\times C_m))=2\rho (\text{ED}(C_m))$. Also in $[2]$, the following question was posed: which digraphs are fixed points under the digraph operator? We provide a proof for the observations about $C_m\times C_m$, and in the process show that these products comprise a family of fixed points under $\text{ED}$. We then provide a number of other interesting examples of fixed point families.

In this paper, we derive some necessary existence conditions for balanced arrays (B-arrays) of strength eight and with two levels by making use of some classical inequalities such as Cauchy, Hölder, and Minkowski. We discuss the usefulness of these conditions in the study of the B-arrays, and also present some illustrative examples.

For a graph $G$ having chromatic number $k$, an equivalence relation is defined on the set $X$ consisting of all proper vertex $k$-colorings of $G$. This leads naturally to an equivalence relation on the set $\mathcal{P}$ consisting of all partitions of $V(G)$ into $k$ independent subsets of color classes. The notion of a partition type arises and the algebra of types is investigated.

We derive a new upper bound of $26$ for the Ramsey number $R(K_5–P_3,K_5)$, lowering the previous upper bound of $28$. This leaves $25\le R(K_5–P_5,K_5)\le 26$, improving on one of the three remaining open cases in Hendry’s table, which listed Ramsey numbers for pairs of graphs $(G,H)$ with $G$ and $H$ having five vertices.

We also show, with the help of a computer, that $R(B_2,B_6)=17$ and $R(B_2,B_7)=18$ by full enumeration of $(B_2,B_6)$-$good$ graphs and $(B_2,B_7)$-$good$ graphs, where $B_n$ is the book graph with $n$ triangular pages.

Let $G$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$, and let ${\mathbb{Z}}_2=\{0,1\}$. Any edge labeling $f$ induces a partial vertex labeling $f^{+}:V(G)\to {\mathbb{Z}}_2$ assigning $0$ or $1$ to $f^{+}(v)$, $v$ being an element of $V(G)$, depending on whether there are more $0$-edges or $1$-edges incident with $v$, and no label is given to $f^{+}(v)$ otherwise. For each $i\in {\mathbb{Z}}_2$, let $v_f(i)=|\{v\in V(G):f^{+}(v)=i\}|$ and let $e_f(i)=|\{e\in E(G):f(e)=i\}|$. An edge-labeling $f$ of $G$ is said to be edge-friendly if $|e_f(0)–e_f(1)|\le 1$. The edge-balance index set of the graph $G$ is defined as $\text{EBI}(G)=\{|v_f(0)–v_f(1)|:f\text{ is edge-friendly}\}$. In this paper, we investigate and present results concerning the edge-balance index sets of $L$-products of cycles with stars.

In [A.G. Chetwynd and A.J.W. Hilton, Critical star multigraphs, Graphs and Combinatorics 2(1986), 209-221], Chetwynd and Hilton started the investigations of the edge-chromatic properties of a particular class of multigraphs, which they called star multigraphs. A star multigraph is a multigraph such that there exists a vertex $v^{\ast }$ that is incident with each multiple edge. Star multigraphs turn out to be useful tools in the study of the chromatic index of simple graphs.

The main goal of this paper is to provide shorter and simpler proofs of all the main theorems contained in the above-mentioned paper. Most simplifications are achieved by means of a formula for the chromatic index recently obtained by the author and by a careful use of arguments involving fans.

The existence of an equivalence subset of rational functions with Fibonacci numbers as coefficients and the Golden Ratio as fixed point is proven. The proof is based on two theorems establishing basic relationships underlying the Fibonacci Sequence, Pascal’s Triangle, and the Golden Ratio.

The degree set $\mathcal{D}(G)$ of a graph $G$ is the set of degrees of its vertices. It has been shown that when the cardinality of $\mathcal{D}(G)$ is $1$ (i.e., $G$ is regular) or $2$ (i.e., $G$ is bi-regular), the balance index set of $G$ has simple structures. In this work, we determine the balance index sets of unicyclic graphs and subclasses of $(p,p+1)$ graphs to demonstrate the application of this recent result. In addition, we give an explicit formula for the balance index sets of subclasses of complete tri-bipartite graphs $G$ ($|\mathcal{D}(G)|=3$). Structural properties regarding the balance index sets of a general graph $G$ and application examples are also presented.

Let $G$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$, and let ${\mathbb{Z}}_2=\{0,1\}$. Any edge labeling $f$ induces a partial vertex labeling $f^{+}:V(G)\to {\mathbb{Z}}_2$ assigning $0$ or $1$ to $f^{+}(v)$, $v$ being an element of $V(G)$, depending on whether there are more $0$-edges or $1$-edges incident with $v$, and no label is given to $f^{+}(v)$ otherwise. For each $i\in {\mathbb{Z}}_2$, let $v_f(i)=|\{v\in V(G):f^{+}(v)=i\}|$ and $e_f(i)=|\{e\in E(G):f(e)=i\}|$. An edge-labeling $f$ of $G$ is said to be edge-friendly if $|e_f(0)–e_f(1)|\le 1$. The edge-balance index set of the graph $G$ is defined as $\text{EBI}(G)=\{|v_f(0)–v_f(1)|:f\text{ is edge-friendly}\}$. In this paper, we investigate and present results concerning the edge-balance index sets of flux capacitors and $L$-products of stars with cycles.

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$, and let $A=\{0,1\}$. A labeling $f:V(G)\to A$ induces a partial edge labeling $f^{\ast }:E(G)\to A$ defined by $f^{\ast }((u,v))=f(u)$ if and only if $f(u)=f(v)$ for each edge $(u,v)\in E(G)$. For $i\in A$, let ${\text{v}}_f(i)=\text{card}\{v\in V(G):f(v)=i\}$ and ${\text{e}}_f(i)=\text{card}\{e\in E(G):f^{\ast }(e)=i\}$. A labeling $f$ of $G$ is said to be friendly if $|{\text{v}}_f(0)–{\text{v}}_f(1)|\le 1$. The balance index set of the graph $G$, $\text{BI}(G)$, is defined as $\{|{\text{e}}_f(0)–{\text{e}}_f(1)|:\text{the vertex labeling }f\text{ is friendly}\}$. We determine the balance index sets of Halin graphs of stars and double stars.

For a graph $G$, the expression $G\stackrel{v}{\to }(a_1,\dots ,a_r)$ means that for any $r$-coloring of the vertices of $G$ there exists a monochromatic $a_i$-clique in $G$ for some color $i\in \{1,\dots ,r\}$. The vertex Folkman numbers are defined as $F_v(a_1,\dots ,a_r;q)=\text{min}\{|V(G)|:G\stackrel{v}{\to }(a_1,\dots ,a_r)\text{ and }{K}_q⊈G\}$. Of these, the only Folkman number of the form $F(\underbrace{2,\dots ,2};r–1)$ which has remained unknown up to this time is $F_v(2,2,2,2,2;4)$.

We show here that $F_v(2,2,2,2,2;4)=16$, which is equivalent to saying that the smallest $6$-chromatic $K_4$-free graph has $16$ vertices. We also show that the sole witnesses of the upper bound $F_v(2,2,2,2,2;4)\le 16$ are the two Ramsey $(4,4)$-graphs on $16$ vertices.

We give cyclic constructions for loop designs with block size $k=3,4,\text{ and }5$, and all values of $v$, and we thereby determine the $(v,\lambda )$ spectrum for LDs with these block sizes. For $k=3,5$ the $(v,\lambda )$ spectrum for LDs is the same as that for cyclic LDs, but this is not true for $k=4$.

A graph is representable modulo $n$ if its vertices can be assigned distinct labels from $\{0,1,2,\dots ,n-1\}$ such that the difference of the labels of two vertices is relatively prime to $n$ if and only if the vertices are adjacent. The representation number $\text{rep}(G)$ is the smallest $n$ such that $G$ has a representation modulo $n$. In this paper, we determine the representation number and the Prague dimension (also known as the product dimension) of a complete graph minus a disjoint union of paths.

Given a graph $G$, let $E$ be the number of edges in $G$. A \emph{vertex-magic edge labeling} of $G$, defined by Wallis [12] in 2001, is a one-to-one mapping from the set of edges onto the set $\{1,2,\dots ,E\}$ with the property that at any vertex the sum of the labels of all the edges incident to that vertex is the same constant. In 2003, Hartnell and Rall [5] introduced a two-player game based on these labelings, and proved some nice results about winning strategies on graphs that contain vertices of degree one. In this paper, we prove results about winning strategies for certain graphs with cycles where the minimum degree is two.

A vertex labeling $f:V\to \{0,1\}$ of the simple graph $G=(V,E)$ induces a partial edge labeling $f^{\ast }:E\to \{0,1\}$ defined by $f^{\ast }(uv)=f(u)$ if and only if $f(u)=f(v)$. Let $v(i)$ and $e(i)$ be the number of vertices and edges, respectively, that are labeled $i$, and define the balance index set of $G$ as $\{|e(0)–e(1)|:|v(0)–v(1)|\le 1\}$. In this paper, we determine the balance index sets of generalized wheels, which are the Zykov sum of a cycle with a null graph.

The channel assignment problem is the problem of assigning radio frequencies to transmitters while avoiding interference. This problem can be modeled and examined using graphs and graph colorings. $L(2,1)$ coloring was first studied by Griggs and Yeh [6] as a model of a variation of the channel assignment problem. A no-hole coloring, introduced in [4], is defined to be an $L(2,1)$ coloring of a graph which uses all the colors $\{0,1,\dots ,k\}$ for some integer $k$. An $L(2,1)$ coloring is irreducible, introduced in [3], if no vertex labels in the graph can be decreased and yield another $L(2,1)$ coloring. A graph $G$ is inh-colorable if there exists an irreducible no-hole coloring on $G$.

We consider the inh-colorability of bipartite graphs and Cartesian products. We obtain some sufficient conditions for bipartite graphs to be inh-colorable. We also find the optimal inh-coloring for some Cartesian products, including grid graphs and the rook’s graph.

Let $G$ be a nontrivial connected graph of order $n$ and $k$ an integer with $2\le k\le n$. For a set $S$ of $k$ vertices of $G$, let $\kappa (S)$ denote the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,\dots ,T_{\ell }$ in $G$ such that $V(T_i)\cap V(T_j)=S$ for every pair $i,j$ of distinct integers with $1\le i,j\le \ell$. A collection $\{T_1,T_2,\dots ,T_{\ell }\}$ of trees in $G$ with this property is called a set of internally disjoint trees connecting $S$. The $k$-connectivity ${\kappa }_k(G)$ of $G$ is defined as ${\kappa }_k(G)=\text{min}\{\kappa (S)\}$, where the minimum is taken over all $k$-element subsets $S$ of $V(G)$. Thus ${\kappa }_2(G)$ is the connectivity $\kappa (G)$ of $G$. In an edge-colored graph $G$ in which adjacent edges may be colored the same, a tree $T$ is a rainbow tree in $G$ if no two edges of $T$ are colored the same. For each integer $\ell$ with $1\le \ell \le {\kappa }_k(G)$, a $(k,\ell )$-rainbow coloring of $G$ is an edge coloring of $G$ (in which adjacent

Given a right-angled triangle of squares in a grid whose horizontal and vertical sides are $n$ squares long, let $N(n)$ denote the maximum number of dots that can be placed into the cells of the triangle such that each row, each column, and each diagonal parallel to the long side of the triangle contains at most one dot. It has been proven that $N_f(n)=\lfloor \frac{2n+1}{3}\rfloor$. In this note, we give a new proof of the upper bound $N_f(n)\le \lfloor \frac{2n+1}{3}\rfloor$ using linear programming techniques.

In 1975, Leech introduced the problem of labeling the edges of a tree with distinct positive integers so that the sums along distinct paths in the tree were distinct, and the set of such path-sums were consecutive starting with one. We generalize this problem to labelings from arbitrary finite Abelian groups, with a particular focus on direct products of the additive group of ${\mathbb{Z}}_2$.

Let $G$ be a simple graph. Any vertex labeling $f:V(G)\to {\mathbb{Z}}_2$ induces an edge labeling $f^{\ast }:E(G)\to {\mathbb{Z}}_2$ according to $f^{\ast }(xy)=f(x)+f(y)$. For each $i\in {\mathbb{Z}}_2$, define $v_f(i)=|\{v\in V(G):f(v)=i\}|$, and $e_f(i)=|\{e\in E(G):f^{\ast }(e)=i\}|$. The friendly index set of the graph $G$ is defined as $\{|e_f(0)–e_f(1)|:|v_f(0)–v_f(1)|\le 1\}$. We determine the friendly index sets of connected $(p,p+1)$-graphs with minimum degree $2$. Many of them form arithmetic progressions. Those that are not miss only the second terms of the progressions.