Let $G$ be a graph of order $n$. In [A. Saito, Degree sums and graphs that are not covered by two cycles, J. Graph Theory 32 (1999), 51–61.], Saito characterized the graphs with ${\sigma }_3(G)\ge n-1$ that are not covered by two cycles. In this paper, we characterize the graphs with ${\sigma }_4(G)\ge n-1$ that are not covered by three cycles. Moreover, to prove our main theorem, we show several new results which are useful in the study of this area.

Let $\mathcal{B}(n,a)$ be the set of bicyclic graphs on $n$ vertices with matching number $\alpha$. In this paper, we characterize the extremal bicyclic graph with minimal Hosoya index and maximal Merrifield-Simmons index in $\mathcal{B}(n,a)$.

A word has a shape determined by its image under the Robinson-Schensted-Knuth correspondence. We show that when a word $w$ contains a separable (i.e., $3142$- and $2413$-avoiding) permutation $\sigma$ as a pattern, the shape of $w$ contains the shape of $\sigma$. As an application, we exhibit lower bounds for the lengths of supersequences of sets containing separable permutations.

Two graphs are defined to be adjointly equivalent if their complements are chromatically equivalent. In $[2,7]$, Liu and Dong et al. give the first four coefficients $b_0$, $b_1$, $b_2$, $b_3$ of the adjoint polynomial and two invariants $R_1$, $R_2$, which are useful in determining the chromaticity of graphs. In this paper, we give the expression of the fifth coefficient $b_4$, which brings about a new invariant $R_3$. Using these new tools and the properties of the adjoint polynomials, we determine the chromatic equivalence class of $\overline{B_{n-9,1,5}}$.

Given a tournament $T=(V,A)$, a subset $X$ of $V$ is an interval of $T$ provided that for any $a,b\in X$ and $x\in V–X$, $(a,x)\in A$ if and only if $(b,x)\in A$. For example, $\mathrm{\varnothing }$, $\{x\}$ ($x\in V$), and $V$ are intervals of $T$, called trivial intervals. A tournament whose intervals are trivial is indecomposable; otherwise, it is decomposable. With each indecomposable tournament $T$, we associate its indecomposability graph $\mathbb{I}(T)$ defined as follows: the vertices of $\mathbb{I}(T)$ are those of $T$ and its edges are the unordered pairs of distinct vertices $\{x,y\}$ such that $T-\{x,y\}$ is indecomposable. We characterize the indecomposable tournaments $T$ whose $\mathbb{I}(T)$ admits a vertex cover of size $2$.

Let $G$ be a simple graph. A harmonious coloring of $G$ is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number $h(G)$ is the least number of colors in such a coloring. In this paper, it is shown that if $T$ is a tree of order $n$ and $\mathrm{\Delta }(T)\ge \frac{n}{2}$, then $h(T)=\mathrm{\Delta }(T)+1$, where $\mathrm{\Delta }(T)$ denotes the maximum degree of $T$. Let $T_1$ and $T_2$ be two trees of order $n_1$ and $n_2$, respectively, and $F=T_1\cup T_2$. In this paper, it is shown that if $\mathrm{\Delta }(T_i)={\mathrm{\Delta }}_i$ and ${\mathrm{\Delta }}_i\ge \frac{n_i}{2}$, for $i=1,2$, then $h(F)\le \mathrm{\Delta }(F)+2$. Moreover, if ${\mathrm{\Delta }}_1={\mathrm{\Delta }}_2=\mathrm{\Delta }\ge \frac{n_i}{2}$, for $i=1,2$, then $h(F)=\mathrm{\Delta }+2$.

Hamming graph $H(n,k)$ has as vertex set all words of length $n$ with symbols taken from a set of $k$ elements. Suppose $L$ denotes the set $\bigcup _{i=0}^{n+1}{\mathrm{\Omega }}_l$ with ${\mathrm{\Omega }}_l=\{\sum _{i\in I_1}{e}_i^1+\sum _{i\in I_2}{e}_i^2+\dots +\sum _{i\in I_k}{e}_i^k|I_j\cap I_j^{\prime }=\mathrm{\varnothing }(j\ne j^{\prime }),|\bigcup _{j=1}^k{I}_j|=l\}$ for $0\le l\le n$ and ${\mathrm{\Omega }}_{n+1}$. For any two elements $x,y\in L$, define $x\le y$ if and only if $y=I$ or $I_j^x\le I_j^y$ for some $1\le j\le k$. Then $L$ is a lattice, denoted by $L_o$. Reversing the above partial order, we obtain the dual of $L_o$, denoted by $L_r$. This article discusses their geometric properties and computes their characteristic polynomials.

The paper considers two-dimensional linear codes with sub-block structure in RT-spaces $[2-5,7]$ whose error location techniques are described in terms of various sub-blocks. Upper and lower-bounds are given for the number of check digits required with any error locating code in RT-spaces.

Let $k\ge 0$ be an integer. Oblong (pronic) numbers are numbers of the form $O_k=k(k+1)$. In this work, we set a new integer sequence $B=B_n(k)$ defined as $B_0=0$, $B_1=1$, and $B_n=O_k{B}_{n-1}–B_{n-2}$ for $n\ge 2$, and then derive some algebraic relations on it. Later, we give some new results on balancing numbers via oblong numbers.

This note deals with the computation of the factorization number $F_2(G)$ of a finite group $G$. By using the Möbius inversion formula, explicit expressions of $F_2(G)$ are obtained for two classes of finite abelian groups, improving the results of “Factorization numbers of some finite groups”, Glasgow Math. J. (2012).

The general sum-connectivity index is defined as ${\chi }_{\alpha }(G)=\sum _{uv\in E(G)}(d_G(u)+d_G(v){)}^{\alpha }$. Let $\mathcal{T}(n,\beta )$ be the class of trees of order $n$ with given matching number $\beta$. In this paper, we characterize the structure of the trees with a given order and matching number that have maximum general sum-connectivity index for $0<\alpha <1$ and give a sharp upper bound for $\alpha \ge 1$.

The hyper-Wiener index is a graph invariant that is used as a structure descriptor for predicting physicochemical properties of organic compounds. We determine the n-vertex unicyclic graphs with the third smallest and the third largest hyper-Wiener indices for $n\ge 5$.

A graph $G$ with no isolated vertex is total restrained domination vertex critical if for any vertex $v$ of $G$ that is not adjacent to a vertex of degree one, the total restrained domination number of $G–v$ is less than the total restrained domination number of $G$. We call these graphs ${\gamma }_{tr}$-vertex critical. If such a graph $G$ has total restrained domination number $k$, we call it $k$-${\gamma }_{tr}$-vertex critical. In this paper, we study matching properties in $4$-${\gamma }_{tr}$-vertex critical graphs of minimum degree at least two.

A generalized weighted digraph $G=(V,E)$ is a digraph with $n$ vertices and $m$ arcs without loops and multiarcs, where each arc is assigned a weight that is a non-negative and symmetric matrix of order $p$. In this paper, we give a sharp upper bound for the spectral radius of generalized weighted digraphs (see Theorem 2.7), which generalizes some other results on the spectral radius of weighted digraphs in [4], [11], and [16].

It has been shown by Bennett et al. in 1998 that a holey Schröder design with $n$ holes of size 2 and one hole of size $u$, i.e., of type $2^{n}u$, exists if $1\le u\le 4$ and $n\ge u+1$ with the exception of $(n,u)\in \{(2,1),(3,1),(3,2)\}$, or $u\ge 16$ and $n\ge \lceil \frac{5u}{4}\rceil +14$. In this paper, we extend this result by showing that, for $1\le u\le 16$, a holey Schröder design of type $2^{n}u$ exists if and only if $n\ge u+1$, with the exception of $(n,u)\in \{(2,1),(3,1),(3,2)\}$ and with the possible exception of $(n,u)\in \{(7,5),(7,6),(11,9),(11,10)\}$. For general $u$, we prove that there exists an HSD($2^{n}u$) for all $u\ge 17$ and $n\ge \lceil \frac{5u}{4}\rceil +4$. Moreover, if $u\ge 35$, then an HSD($2^{n}u$) exists for all $n\ge \lceil \frac{5u}{4}\rceil +1$; if $u\ge 95$, then an HSD($2^{n}u$) exists for all $n\ge \lceil \frac{5u}{4}\rceil –2$. We also improve a well-known result on the existence of holey Schröder designs of type $h^n$ by removing the remaining possible exception of type $64$.

A vertex of a graph is said to be total domination critical if its deletion decreases the total domination number. A graph is said to be total domination vertex critical if all of its vertices, except the supporting vertices, are total domination vertex critical. We show that if $G$ is a connected total domination vertex critical graph with total domination number $k\ge 4$, then the diameter of $G$ is at most $\lfloor \frac{5k-7}{3}\rfloor$.

By computer-assisted approaches and inductive arguments, two curious sums of triple multiplication of binomial coefficients are established in the present paper. The two curious sums arise in proving Melham’s conjecture on odd power sums of Fibonacci numbers, which was confirmed by Xie, Yang and the present author. However, being different from their’s technical way, the method used in the paper is more elementary.

Let $G$ be a graph and $u$ be a vertex of $G$. The transmission index of $u$ in $G$, denoted by $T_G(u)$, is the sum of distances from $u$ to all the other vertices in graph $G$, i.e., $T(u)=T_G(u)=\sum _{v\in V}{d}_G(u,v)$. The Co-PI index [1] is defined as $Co\text{-}PI(G)=\sum _{uv\in E(G)}|T(u)–T(v)|$. In this paper, we give some upper bounds for the Co-PI indices of the join, composition, disjunction, symmetric difference, and corona graph $G_1\circ G_2$.

The purpose of this note is the study of the hypergroups associated with binary relations. New types of matrices, called $i$-very good and regular reversible matrices, are introduced in order to give some properties of the Rosenberg hypergroups related to them. A program written in MATLAB computes the number of these hypergroups up to isomorphism.

Let $A_n$ be the alternating group of degree $n$ with $n>4$. Set $T=\{(123),(132),(12)(3i)\mid 4\le i\le n\}$. The alternating group network, denoted by $A{N}_n$, is defined as the Cayley graph on $A_n$ with respect to $T$. Some properties of $A{N}_n$ have been investigated in [App. Math.—JCU, Ser. A 14 (1998) 235-239; IEEE Trans. Comput. 55 (2006) 1645-1648; Inform. Process. Lett. 110 (2010) 403-409; J. Supercomput. 54 (2010) 206-228]. In this paper, it is shown that the full automorphism group of $A{N}_n$ is the semi-direct product $R(A_n)⋊\text{Aut}(A_n,T)$, where $R(A_n)$ is the right regular representation of $A_n$ and $\text{Aut}(A_n,T)=\{\alpha \in \text{Aut}(A_n)\mid T^{\alpha }=T\}\cong S_{n-3}\times S_2$.

The harmonic index of a graph $G$ is defined as the sum of weights $\frac{2}{\mathrm{deg}(v)+\mathrm{deg}(u)}$ of all edges $uv$ in $E(G)$, where $\mathrm{deg}(v)$ denotes the degree of a vertex $v$ in $V(G)$. In this note, we generalize results of [L. Zhong, The harmonic index on graphs, Appl. Math. Lett. 25 (2012), 561-566] and establish some upper and lower bounds on the harmonic index of $G$.

Let ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ be the eigenvalues of the distance matrix of a connected graph $G$. The distance Estrada index of $G$ is defined as $DEE(G)=\sum _{i=1}^n{e}^{{\lambda }_i}$. In this note, we present new lower and upper bounds for $DEE(G)$. In addition, a Nordhaus-Gaddum type inequality for $DEE(G)$ is given.

The splitting-off operation has important applications for graph connectivity problems. Shikare, Dalvi, and Dhotre [splitting-off operation for binary matroids and its applications, Graphs and Combinatorics, $27(6)(2011),871–882$] extended this operation to binary matroids. In this paper, we provide a sufficient condition for preserving $n$-connectedness of a binary matroid under the splitting-off operation.

For positive integers $j$ and $k$ with $j>k$, an $L(j,k)$-labelling is a generalization of classical graph coloring where adjacent vertices are assigned integers at least $j$ apart, and vertices at distance two are assigned integers at least $k$ apart. The span of an $L(j,k)$-labelling of a graph $G$ is the difference between the maximum and minimum integers assigned to its vertices. The $L(j,k)$-labelling number of $G$, denoted by ${\lambda }_{j,k}(G)$, is the minimum span over all $L(j,k)$-labellings of $G$. An $m$-$(j,k)$-circular labelling of $G$ is a function $f:V(G)\to \{0,1,\dots ,m-1\}$ such that $|f(u)-f(v){|}_m\ge j$ if $u$ and $v$ are adjacent, and $|f(u)-f(v){|}_m\ge k$ if $u$ and $v$ are at distance two, where $|x{|}_m=min\{|x|,m-|x|\}$. The span of an $m$-$(j,k)$-circular labelling of $G$ is the difference between the maximum and minimum integers assigned to its vertices. The $m$-$(j,k)$-circular labelling number of $G$, denoted by ${\sigma }_{j,k}(G)$, is the minimum span over all $m$-$(j,k)$-circular labellings of $G$. The $L^{\prime }(j,k)$-labelling is a one-to-one $L(j,k)$-labelling, and the $m$-$(j,k{)}^{\prime }$-circular labelling is a one-to-one $m$-$(j,k)$-circular labelling. Denote ${\lambda }_{j,k}^{\prime }(G)$ the $L^{\prime }(j,k)$-labelling number and ${\sigma }_{j,k}^{\prime }(G)$ the $m$-$(j,k{)}^{\prime }$-circular labelling number. When $j=d,k=1$, $L(j,k)$-labelling becomes $L(d,1)$-labelling. [Discrete Math. 232 (2001) 163-169] determined the relationship between ${\lambda }_{2,1}(G)$ and ${\sigma }_{2,1}(G)$ for a graph $G$. We generalized the concept of path covering to the $t$-group path covering (Inform Process Lett (2011)) of a graph. In this paper, using group path covering, we establish relationships between ${\lambda }_{4,1}(G)$ and ${\sigma }_{4,1}(G)$ and between ${\lambda }_{j,k}(G)$ and ${\sigma }_{j,k}(G)$ for a graph $G$ with diameter 2. Using these results, we obtain shorter proofs for the ${\sigma }_{j,k}^{\prime }$-number of Cartesian products of complete graphs [J Comb Optim (2007) 14: 219-227].

We prove the following Turdn-Type result: If there are more than $9mn/16$ edges in a simple and bipartite Eulerian digraph with vertex partition size m and n, then the graph contains a directed cycle of length $4$ or $6$. By using this result, we improve an upper bound for the diameter of interchange graphs.

The well known infinite families of prisms and antiprisms on the sphere were, for long time, not considered as Archimedean solids for reasons not fully understood. In this paper we describe the first two infinite families of Archimedean maps on higher genera which we call “generalized” prisms and “generalized” antiprisms.

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. A vertex labeling $f:V(G)\to {\mathbb{Z}}_2$ induces an edge labeling $f^{\ast }:E(G)\to {\mathbb{Z}}_2$ defined by $f^{\ast }(x,y)=f(x)+f(y)$, for each edge $(x,y)\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\}|$. A vertex labeling $f$ of a graph $G$ is said to be friendly if $|v_f(1)–v_f(0)|\le 1$. The friendly index set of the graph $G$, denoted by $FI(G)$, is defined as $\{|v_f(1)–v_f(0)|:\text{the vertex labeling }f\text{ is friendly}\}$. The full friendly index set of the graph $G$, denoted by $FFI(G)$, is defined as $\{|e_f(1)–e_f(0)|:\text{the vertex labeling }f\text{ is friendly}\}$. In this paper, we determine $FFI(G)$ and $FI(G)$ for a class of cubic graphs which are twisted products of Möbius.

Let $k$ be a non-negative integer. Two digraphs $G=(V,A)$ and $G^{\prime }=(V,A^{\prime })$ are $\{k\}$-hypomorphic if for all $k$-element subsets $K$ of $V$, the subdigraphs $G[K]$ and $G^{\prime }[K]$ induced on $K$ are isomorphic. The equivalence relation ${\mathcal{D}}_{G,G^{\prime }}$ on $V$ is defined by: $x{\mathcal{D}}_{G,G^{\prime }}y$ if $x=y$ or there exists a sequence $x_0=x,\dots ,x_n=y$ of elements of $V$ satisfying $(x_i,x_{i+1})\in A$ if and only if $(x_i,x_{i+1})\in A^{\prime }$, for all $i$, $0<ik+6$. If $G$ and $G^{\prime }$ are two digraphs, $\{4\}$-hypomorphic and $\{v–k\}$-hypomorphic on the same vertex set $V$ of $uv$ vertices, and $C$ is an equivalence class of the equivalence relation ${\mathcal{D}}_{G,G^{\prime }}$, then $G^{\prime }[C\setminus A]$ and $G[C\setminus A]$ are isomorphic for all subsets $A$ of $V$ of at most $k$ vertices. In particular, $G^{\prime }[C]$ and $G[C]$ are $\{v–k–h\}$-hypomorphic for all $h\in \{1,2,\dots ,k\}$, and $G^{\prime }[C]$ and $G[C]$ (resp. $G^{\prime }$ and $G$) are isomorphic. In particular, for $k=1$ and $k=4$ we obtain the result of G. Lopez and C. Rauzy [7]. As an application of the main result, we have: If $G$ and $G^{\prime }$ are $\{v–4\}$-hypomorphic on the same vertex set $V$ of $v>10$ vertices, then $G[X]$ and $G^{\prime }[X]$ are isomorphic for all subsets $X$ of $V$; the particular case of tournaments was obtained by Y. Boudabbous [2].

We prove that each graph in two infinite families is fixed uniquely by just two of its maximal induced subgraphs, with each of which the degree of the missing vertex is also given. One of these families contains all separable self-complementary graphs and a self-complementary graph of diameter $3$ and order $n$ for each $n\ge 5$ such that $n\equiv 0$ or $1(\mathrm{mod}4)$. The other contains a Hamiltonian self-complementary graph of diameter $2$ and order $n$ for each admissible $n\ge 8$.

Restricted strong partially balanced $t$-designs were first formulated by Pei, Li, Wang, and Safavi-Naini in their investigation of authentication codes with arbitration. We recently proved that optimal splitting authentication codes that are multi-fold perfect against spoofing can be characterized in terms of restricted strong partially balanced $t$-designs. This article investigates the existence of optimal restricted strong partially balanced 2-designs, ORSPBD$(v,2\times 4,1)$, and shows that there exists an ORSPBD$(v,2\times 4,1)$ for even $v$. As its application, we obtain a new infinite class of 2-fold perfect $4$-splitting authentication codes.

The $3$-consecutive vertex coloring number ${\psi }_{3c}(G)$ of a graph $G$ is the maximum number of colors permitted in a coloring of the vertices of $G$ such that the middle vertex of any path $P_3$ in $G$ has the same color as one of the ends of that $P_3$. This coloring constraint exactly means that no $P_3$ subgraph of $G$ is properly colored in the classical sense. The $3$-consecutive edge coloring number ${\psi }_{3c}^{\prime }$ is the maximum number of colors permitted in a coloring of the edges of $G$ such that the middle edge of any sequence of three edges (in a path $P_3$ or cycle $C_3$) has the same color as one of the other two edges. For graphs $G$ of minimum degree at least $2$, denoting by $L(G)$ the line graph of $G$, we prove that there is a bijection between the $3$-consecutive vertex colorings of $G$ and the $3$-consecutive edge colorings of $L(G)$, which keeps the number of colors unchanged, too. This implies that ${\psi }_{3c}={\psi }_{3c}^{\prime }(L(G))$; i.e., the situation is just the opposite of what one would expect at first sight.

Let $p$ be an odd prime, $q$ be a prime power coprime to $p$, and $n$ be a positive integer. For any positive integer $d\le n$, let $g_1(x)=x^{p^{n-d}}–1$,$g_2(x)=1+x^{p^{n–d+1}}+x^{2p^{n-d+1}}+\dots +x^{(p^{d-1}-1)p^{n-d+1}}$,and , $g_3(x)=1+x^{p^{n-d}}+x^{2p^{n-d}}+\dots +x^{(p-1)p^{n-d}}$. In this paper, we determine the weight distributions of $q$-ary cyclic codes of length $pn$ generated by the polynomials $g_1(x)$, $g_2(x)$, $g_3(x)$, $g_4(x)$, and $g_5(x)$, by employing the techniques developed in Sharma \& Bakshi [11]. Keywords: cyclic codes, Hamming weight, weight spectrum.