Authors:Jason DeVito et al. Abstract: For $G$ a simple, connected graph, a vertex labeling $f:V(G)\to \Z_+$ is called a \emph{radio labeling of $G$} if it satisfies $ f(u)-f(v) \geq\diam(G)+1-d(u,v)$ for all distinct vertices $u,v\in V(G)$. The \emph{radio number of $G$} is the minimal span over all radio labelings of $G$. If a bijective radio labeling onto $\{1,2,\dots, V(G) \}$ exists, $G$ is called a \emph{radio graceful} graph. We determine the radio number of all diameter 3 Hamming graphs and show that an infinite subset of them is radio graceful. PubDate: Thu, 25 Aug 2022 04:41:08 PDT

Authors:Kazhal Haghparast et al. Abstract: A set $S$ of vertices is a restrained dominating set of a graph $G=(V,E)$ if every vertex in $V\setminus S$ has a neighbor in $S$ and a neighbor in $V\setminus S$. The minimum cardinality of a restrained dominating set is the restrained domination number $\gamma_{r}(G)$. In this paper we initiate the study of the restrained reinforcement number $r_{r}(G)$ of a graph $G$ defined as the cardinality of a smallest set of edges $F\subseteq E(\overline{G})$ for which $\gamma _{r}(G+F) PubDate: Wed, 24 Aug 2022 04:31:31 PDT

Authors:Wai Chee Shiu et al. Abstract: Let $A$ be a nontrivial abelian group. A connected simple graph $G = (V, E)$ is $A$-\textbf{antimagic} if there exists an edge labeling $f: E(G) \to A \setminus \{0\}$ such that the induced vertex labeling $f^+: V(G) \to A$, defined by $f^+(v) = \Sigma$ $\{f(u,v): (u, v) \in E(G) \}$, is a one-to-one map. In this paper, we analyze the group-antimagic property for Cartesian products, hexagonal nets and theta graphs. PubDate: Wed, 24 Aug 2022 04:31:20 PDT

Authors:Sethuraman G et al. Abstract: The total chromatic number of a graph $G$, denoted $\chi^{\prime\prime}(G)$, is the least number of colours needed to colour the vertices and the edges of $G$ such that no incident or adjacent elements (vertices or edges) receive the same colour. The popular Total Colouring Conjecture (TCC) posed by Behzad states that, for every simple graph $G$, $\chi^{\prime\prime}(G) \leq \Delta(G)+2$. In this paper, we prove that the total chromatic number for a family of subcubic graphs called cube connected paths and also for a class of subcubic graphs having the property that the vertices are covered by independent triangles are exactly $\Delta(G)+1$. More precisely, these two families of subcubic graphs are shown to be Type 1 graph.\\ PubDate: Wed, 24 Aug 2022 04:31:10 PDT

Authors:Amruta V. Shinde et al. Abstract: A cycle containing a shortest path between two vertices $u$ and $v$ in a graph $G$ is called a $(u,v)$-geodesic cycle. A connected graph $G$ is geodesic 2-bipancyclic, if every pair of vertices $u,v$ of it is contained in a $(u,v)$-geodesic cycle of length $l$ for each even integer $l$ satisfying $2d + 2\leq l \leq V(G) ,$ where $d$ is the distance between $u$ and $v.$ In this paper, we prove that the Cartesian product of two geodesic hamiltonian graphs is a geodesic 2-bipancyclic graph. As a consequence, we show that for $n \geq 2$ every $n$-dimensional torus is a geodesic 2-bipancyclic graph. PubDate: Mon, 18 Jul 2022 14:06:16 PDT

Authors:Mark Anthony C. Tolentino et al. Abstract: Given a vertex coloring c of a graph, the neighborhood color set of a vertex is defined to be the set of all of its neighbors’ colors. The coloring c is called a set coloring if any two adjacent vertices have different neighborhood color sets. The set chromatic number χs(G) of a graph G is the minimum number of colors required in a set coloring of G. In this work, we investigate a total analog of set colorings; that is, we study set colorings of the total graph of graphs. Given a graph G = (V, E), its total graph T(G) is the graph whose vertex set is V ∪ E and in which two vertices are adjacent if and only if their corresponding elements in G are adjacent or incident. First, we establish sharp bounds for the set chromatic number of the total graph of a graph. Furthermore, we study the set colorings of the total graph of different families of graphs. PubDate: Mon, 18 Jul 2022 14:06:05 PDT

Authors:Jared L. Painter et al. Abstract: In \cite{AR}, it is shown that the disjoint union of an odd cycle and certain paths is harmonious, and that certain starlike trees are harmonious using properties of cosets for a particular subgroup of $\mathbb{Z}_m$, where $m$ is the number of edges of the graph. We expand upon these results by first exploring the numerical properties when adding values from cosets and subcosets in $\mathbb{Z}_m$. We will then show that these properties may be used to harmoniously label graphs involving a more complex starlike tree, which we will call the snowflake graph. PubDate: Mon, 18 Jul 2022 14:01:21 PDT

Authors:Kuniharu Yokomura et al. Abstract: For a digraph $D$, the $p$-competition graph $C_{p}(D)$ of $D$ is the graph satisfying the following: $V(C_{p}(D))=V(D)$, for $x,y \in V(C_{p}(D))$, $xy \in E(C_{p}(D))$ if and only if there exist distinct $p$ vertices $v_{1},$ $v_{2},$ $...,$ $v_{p}$ $\in$ $V(D)$ such that $x \rightarrow v_{i}$, $y \rightarrow v_{i}$ $\in$ $A(D)$ for each $i=1,2,$ $...,$ $p$.We show the $H_1 \cup H_2$ is a $p$-competition graph of a loopless digraph without symmetric arcs for $p \geq 2$, where $H_1$ and $H_2$ are $p$-competition graphs of loopless digraphs without symmetric arcs and $V(H_1) \cap V(H_2)$ $=$ $\{ \alpha \}$. For $p$-competition graphs of loopless Hamiltonian digraphs without symmetric arcs, we obtain similar results. And we show that a star $K_{1,n}$ is a $p$-competition graph of a loopless Hamiltonian digraph without symmetric arcs if $n \geq 2p+3$ and $p \geq 3$.Based on these results, we obtain conditions such that spiders, caterpillars and cacti are $p$-competition graphs of loopless digraphs without symmetric arcs. We also obtain conditions such that these graphs are $p$-competition graphs of loopless Hamiltonian digraphs without symmetric arcs. PubDate: Mon, 18 Jul 2022 14:01:10 PDT

Authors:György Kiss et al. Abstract: There are three types of affine regular polygons in AG(2, q): ellipse, hyperbola and parabola. The first two cases have been investigated in previous papers. In this note, a particular class of geometric one-factorizations of the complete graph Kn arising from parabolas is constructed and described in full detail. With the support of computer aided investigation, it is also conjectured that up to isomorphisms this is the only one-factorization where each one-factor is either represented by a line or a parabola. PubDate: Wed, 06 Jul 2022 06:51:26 PDT

Authors:Naoki Matsumoto Abstract: A {\em $k$-domination number} of a graph $G$ is minimum cardinality of a $k$-dominating set of $G$, where a subset $S \subseteq V(G)$ is a {\em $k$-dominating set} if each vertex $v\in V(G)\setminus S$ is adjacent to at least $k$ vertices in $S$. It is known that for any graph $G$ with $\Delta(G) \geq k \geq 2$, $\gamma_k(G) \geq \gamma(G) + k - 2$, and then $\gamma_k(G)> \gamma(G)$ for any $k\geq 3$, where $\gamma(G) = \gamma_1(G)$ is the usual domination number. Thus, it is the most interesting problem to characterize graphs $G$ with $\gamma_2(G) = \gamma(G)$. In this paper, we characterize outerplanar graphs with equal 2-domination and domination numbers. PubDate: Wed, 06 Jul 2022 06:51:17 PDT

Authors:Shuhei Saitoh et al. Abstract: Given an edge-colored complete graph Kn on n vertices, a perfect (respectively, near-perfect) matching M in Kn with an even (respectively, odd) number of vertices is rainbow if all edges have distinct colors. In this paper, we consider an edge coloring of Kn by circular distance, and we denote the resulting complete graph by K●n. We show that when K●n has an even number of vertices, it contains a rainbow perfect matching if and only if n=8k or n=8k+2, where k is a nonnegative integer. In the case of an odd number of vertices, Kirkman matching is known to be a rainbow near-perfect matching in K●n. However, real-world applications sometimes require multiple rainbow near-perfect matchings. We propose a method for using a recursive algorithm to generate multiple rainbow near-perfect matchings in K●n. PubDate: Sat, 25 Jun 2022 04:01:11 PDT

Authors:Viktoriia Viktorivna Bilet et al. Abstract: Let \((X, d)\) be a semimetric space and let \(G\) be a graph. We say that \(G\) is the diametrical graph of \((X, d)\) if \(X\) is the vertex set of \(G\) and the adjacency of vertices \(x\) and \(y\) is equivalent to the equality \(\diam X = d(x, y)\). It is shown that a semimetric space \((X, d)\) with diameter \(d^*\) is ultrametric iff the diametrical graph of \((X, d_{\varepsilon})\) with \(d_{\varepsilon}(x, y) = \min\{d(x, y), \varepsilon\}\) is complete multipartite for every \(\varepsilon \in (0, d^*)\). A refinement of the last result is given for totally bounded ultrametric spaces. Moreover, using complete multipartite graphs we characterize the compact ultrametrizable topological spaces. The bounded ultrametric spaces, which are weakly similar to unbounded ones, are also characterized via complete multipartite graphs. PubDate: Sat, 25 Jun 2022 03:51:13 PDT

Authors:SeungJae Eom et al. Abstract: An even 2-factor is one such that each cycle is of even length. A 4- regular graph G is 4-edge-colorable if and only if G has two edge-disjoint even 2- factors whose union contains all edges in G. It is known that the line graph of a cubic graph without 3-edge-coloring is not 4-edge-colorable. Hence, we are interested in whether those graphs have an even 2-factor. Bonisoli and Bonvicini proved that the line graph of a connected cubic graph G with an even number of edges has an even 2-factor, if G has a perfect matching [Even cycles and even 2-factors in the line graph of a simple graph, Electron. J. Combin. 24 (2017), P4.15]. In this paper, we extend this theorem to the line graph of a connected cubic graph G satisfying certain conditions. PubDate: Thu, 19 May 2022 11:56:05 PDT

Authors:Stephen James Curran Abstract: It is known that for any prime p and any integer n such that 1≤n≤p there exists a prime labeling on the pxn planar grid graph PpxPn. We show that PpxPn has a prime labeling for any odd prime p and any integer n such that that p PubDate: Thu, 24 Mar 2022 07:06:37 PDT

Authors:Jana Coroničová Hurajová et al. Abstract: The \emph{betweenness centality} of an edge $e$ is, summed over all $u,v\in V(G)$, the ratio of the number of shortest $u,v$-paths in $G$ containing $e$ to the number of shortest $u,v$-paths in $G$. Graphs whose vertices all have the same edge betweenness centrality are called \emph{edge betweeness-uniform}. It was recently shown by Madaras, Hurajová, Newman, Miranda, Fl\'{o}rez, and Narayan that of the over 11.7 million graphs with ten vertices or fewer, only four graphs are edge betweenness-uniform but not edge-transitive.In this paper we present new results involving properties of betweenness-uniform graphs. PubDate: Thu, 24 Mar 2022 07:06:27 PDT

Authors:Deepak Sehrawat et al. Abstract: For $m \geq 3$ and $n \geq 1$, the $m$-cycle \textit{book graph} $B(m,n)$ consists of $n$ copies of the cycle $C_m$ with one common edge. In this paper, we prove that (a) the number of switching non-isomorphic signed $B(m,n)$ is $n+1$, and (b) the chromatic number of a signed $B(m,n)$ is either 2 or 3. We also obtain explicit formulas for the chromatic polynomials and the zero-free chromatic polynomials of switching non-isomorphic signed book graphs. PubDate: Thu, 24 Mar 2022 07:06:16 PDT

Authors:Richard M. Low et al. Abstract: Let $A$ be a nontrivial abelian group and $A^* = A \setminus \{0\}$. A graph is $A$-magic if there exists an edge labeling $f$ using elements of $A^*$ which induces a constant vertex labeling of the graph. Such a labeling $f$ is called an $A$-magic labeling and the constant value of the induced vertex labeling is called an $A$-magic value. In this paper, we use the Combinatorial Nullstellensatz to show the existence of $\mathbb{Z}_p$-magic labelings (prime $p \geq 3$ ) for various graphs, without having to construct the $\mathbb{Z}_p$-magic labelings. Through many examples, we illustrate the usefulness (and limitations) in applying the Combinatorial Nullstellensatz to the integer-magic labeling problem. Finally, we focus on $\mathbb{Z}_3$-magic labelings and give some results for various classes of graphs. PubDate: Tue, 22 Feb 2022 14:46:32 PST

Authors:Remie Janssen et al. Abstract: The unit distance graph $G^1_{R^d}$ is the infinite graph whose nodes are points in $R^d$, with an edge between two points if the Euclidean distance between these points is $1$. The 2-dimensional version $G^1_{R^2}$ of this graph is typically studied for its chromatic number, as in the Hadwiger-Nelson problem. However, other properties of unit distance graphs are rarely studied. Here, we consider the restriction of $G^1_{R^d}$ to closed convex subsets $X$ of $R^d$. We show that the graph $G^1_{R^d}[X]$ is connected precisely when the radius of $r(X)$ of $X$ is equal to $0$, or when $r(X)\geq 1$ and the affine dimension of $X$ is at least $2$. For hyperrectangles, we give bounds for the graph diameter in the critical case that the radius is exactly 1. PubDate: Tue, 22 Feb 2022 14:41:33 PST

Authors:Naoki Matsumoto et al. Abstract: A (not necessarily proper) $k$-coloring $c : V(G) \rightarrow \{1,2,\dots,k\}$ of a graph $G$ on a surface is a {\em facial $t$-complete $k$-coloring} if every $t$-tuple of colors appears on the boundary of some face of $G$. The maximum number $k$ such that $G$ has a facial $t$-complete $k$-coloring is called a {\em facial $t$-achromatic number} of $G$, denoted by $\psi_t(G)$. In this paper, we investigate the relation between the facial 3-achromatic number and guarding number of triangulations on a surface, where a {\em guarding number} of a graph $G$ embedded on a surface, denoted by $\gd(G)$, is the smallest size of its {\em guarding set} which is a generalized concept of guards in the art gallery problem. We show that for any graph $G$ embedded on a surface, $\psi_{\Delta(G^*)}(G) \leq \gd(G) + \Delta(G^*) - 1$, where $\Delta(G^*)$ is the largest face size of $G$. Furthermore, we investigate sufficient conditions for a triangulation $G$ on a surface to satisfy $\psi_{3}(G) = \gd(G) + 2$. In particular, we prove that every triangulation $G$ on the sphere with $\gd(G) = 2$ satisfies the above equality and that for one with guarding number $3$, it also satisfies the above equality with sufficiently large number of vertices. PubDate: Wed, 16 Feb 2022 09:26:17 PST

Authors:Willie Han Wah Wong et al. Abstract: For a connected graph $G$, let $\mathscr{D}(G)$ be the family of strong orientations of $G$; and for any $D\in\mathscr{D}(G)$, we denote by $d(D)$ the diameter of $D$. The $\textit{orientation number}$ of $G$ is defined as $\bar{d}(G)=\min\{d(D)\mid D\in \mathscr{D}(G)\}$. In 2000, Koh and Tay introduced a new family of graphs, $G$ vertex-multiplications, and extended the results on the orientation number of complete $n$-partite graphs. Suppose $G$ has the vertex set $V(G)=\{v_1,v_2,\ldots, v_n\}$. For any sequence of $n$ positive integers $(s_i)$, a $G$ \textit{vertex-multiplication}, denoted by $G(s_1, s_2,\ldots, s_n)$, is the graph with vertex set $V^*=\bigcup_{i=1}^n{V_i}$ and edge set $E^*$, where $V_i$'s are pairwise disjoint sets with $ V_i =s_i$, for $i=1,2,\ldots,n$; and for any $u,v\in V^*$, $uv\in E^*$ if and only if $u\in V_i$ and $v\in V_j$ for some $i,j\in \{1,2,\ldots, n\}$ with $i\neq j$ such that $v_i v_j\in E(G)$. They proved a fundamental classification of $G$ vertex-multiplications, with $s_i\ge 2$ for all $i=1,2,\ldots, n$, into three classes $\mathscr{C}_0, \mathscr{C}_1$ and $\mathscr{C}_2$, and any vertex-multiplication of a tree with diameter at least 3 does not belong to the class $\mathscr{C}_2$. Furthermore, some necessary and sufficient conditions for $\mathscr{C}_0$ were established for vertex-multiplications of trees with diameter $5$. In this paper, we give a complete characterisation of vertex-multiplications of trees with diameter $5$ in $\mathscr{C}_0$ and $\mathscr{C}_1$. PubDate: Mon, 15 Nov 2021 10:31:27 PST