Let $G$ be a non-abelian group and let $Z(G)$ be the center of $G$. Associate with $G$ a graph ${\mathrm{\Gamma }}_G$ as follows: Take $G\setminus Z(G)$ as vertices of ${\mathrm{\Gamma }}_G$ and join two distinct vertices $x$ and $y$ whenever $xy\ne yx$. Graph ${\mathrm{\Gamma }}_G$ is called the non-commuting graph of $G$ and many of graph theoretical properties of ${\mathrm{\Gamma }}_G$ have been studied. In this paper, we study some metric graph properties of ${\mathrm{\Gamma }}_G$.

For integers $p$, $q$, $s$ with $p\ge q\ge 2$ and $s\ge 0$, let ${\mathcal{K}}_2^{-s}(p,q)$ denote the set of $2$-connected bipartite graphs which can be obtained from the complete bipartite graph $K_{p,q}$ by deleting a set of $s$ edges. F.M.Dong et al. (Discrete Math. vol.$224(2000)107-124$) proved that for any graph $G\in {\mathcal{K}}_2^{-s}(p,q)$ with $p\ge q\ge 3$ and $0\le s\le min\{4,q-1\}$, then $G$ is chromatically unique. In $[13]$, we extended this result to $s=5$ and $s=6$. In this paper, we consider the case when $s=7$.

Let $\lambda K_{h^u}$ denote the $\lambda$-fold complete multipartite graph with $u$ parts of size $h$. A cube factorization of $\lambda K_{h^u}$ is a uniform $3$-factorization of $\lambda K_{h^u}$ in which the components of each factor are cubes. We show that there exists a cube factorization of $\lambda K_{h^u}$ if and only if $uh\equiv 0(\mathrm{mod}8)$, $\lambda (u-1)h\equiv 0(\mathrm{mod}3)$, and $u\ge 2$. It gives a new family of uniform $3$-factorizations of $\lambda K_{h^u}$. We also establish the necessary and sufficient conditions for the existence of cube frames of $\lambda K_{h^u}$.

We recall from [13] a shell graph of size $n$, denoted $C(m,n-3)$, is the graph obtained from the cycle $C_n(v_0,v_1,v_2\dots ,v_{n-1})$ by adding $m-3$ consecutive chords incident at a common vertex, say $v_0$. The vertex $v_0$ of $C(n,n-3)$ is called the apex of the shell $C(n,n-3)$. The vertex $v_0$ of $C(n,n-3)$ is said to be at level $l$.

A graph $C(2n,n-2)$ is called an alternate shell, if $C(2n,n-2)$ is obtained from the cycle $C2n(v_0,v_1,v_2\dots ,v_{2n-1})$ by adding $n-2$ chords between the vertex $v_0$ and the vertices $v_{2i-1}$ for $1-i\delta n$. If the vertex $v_i$ of $C(2n,n-2)$ at level $l$ and is adjacent with $v_0$, then $v_l$ is said to be at level $l$ with a chord, otherwise the vertex $v_i$ is said to be at level $l$ without a chord.

A graph, denoted $G2n_i,n_i,2,k,l$, is called one vertex union of alternate shells with a path at any common level $l$ (with or without chords), if it is obtained from $k$ alternate shells $C(2n_i,n_i-2{)}^{\prime }s$, $1-i\delta k$, by merging them together at their apex and joining $k$ vertices each chosen from a distinct alternate shell in a particular level $l$ (with or without chords) by a path $P_{2k-1}$, such that the chosen vertex of the $i$th alternate shell $C(2n_i,n_i-2)$ is at the $(2i-1)$th vertex of the $P_{2k-l}$ for $1-i\delta k$. We denote the graph $G2n_i,n_i,2,k,l$ as $G2n_i,n_i,2,k,l_c$ if the path $P_{2k-1}$ joins the vertices only at the common level $l$ with chords.

In this paper, we show that $G2n_i,n_i,2,k,l_c$ is graceful and admits an $A$-labeling, for $k-\tau 1,n_i$, $3,1\tau 1,n_i$, and $G2n_i,n_i,2,k,1$ is cordial, for $n_i-n-3,k-1,1\tau i$.

A $(k,t)$-list assignment $L$ of a graph $G$ is a mapping which assigns a set of size $k$ to each vertex $v$ of $G$ and $|\bigcup _{v\in V(G)}L(v)|=t$. A graph $G$ is $(k,t)$-choosable if $G$ has a proper coloring $f$ such that $f(v)\in L(v)$ for each $(k,t)$-list assignment $L$.

We determine $t$ in terms of $k$ and $n$ that guarantee $(k,t)$-choosability of any $n$-vertex graph and a better bound if such graph does not contain a $(k+1)$-clique.

For paths $P_n$, Chartrand, Nebesky and Zhang gave the exact value of $a{c}^{\prime }(P_n)$ for $n\le 8$, and showed that $a{c}^{\prime }(P_n)\le (\genfrac{}{}{0ex}{}{n-2}{2})+2$ for every positive integer $n$, where $a{c}^{\prime }(P_n)$ denotes the nearly antipodal chromatic number of $P_n$. In this paper, we determine the exact values of $a{c}^{\prime }(P_n)$ for all even integers $n\ge 8$.

A $2$-factor of a graph $G$ is a $2$-regular spanning subgraph of $G$ and a $2$-factorization of a graph $G$ is a $2$-factor decomposition of $G$. A complete solution to the problem of determining the spectrum of $4$-cycles in $2$-factorizations of the complete bipartite graph is presented.

We study the independence number of the Cartesian product of binary trees and more general bipartite graphs. We give necessary and sufficient conditions on bipartite graphs under which certain upper and lower bounds on the independence number of the product are equal. A basic tool will be an algorithm for finding the independence number of a binary tree.

Multireceiver authentication codes allow one sender to construct an authenticated message for a group of receivers such that each receiver can verify the authenticity of the received message. In this paper, we construct two multireceiver authentication codes from symplectic geometry over finite fields. The parameters and the probabilities of deceptions of the codes are also computed.

We give determinant expressions of the zeta function and an $L$-function of a semiregular weighted bipartite graph. As an application, we present a decomposition formula for the weighted complexity of a semiregular weighted bipartite graph.