In this note, we determine the exact value for the second largest eigenvalue of the derangement graph, by deriving a formula for all the eigenvalues corresponding to the \(2\)-part partitions. This result is then used to obtain.

Since ancient times, mathematicians have considered geometrical objects with integral side lengths. We consider plane integral point sets \(P\), which are sets of \(n\) points in the plane with pairwise integral distances, where not all the points are collinear.

The largest occurring distance is called its diameter. Naturally, the question about the minimum possible diameter \(d(2, 7)\) of a plane integral point set consisting of \(7\) points arises. We give some new exact values and describe state-of-the-art algorithms to obtain them. It turns out that plane integral point sets with minimum diameter consist very likely of subsets with many collinear points. For this special kind of point sets, we prove a lower bound for \(d(2, n)\) achieving the known upper bound \(n^{c_2\log \log n }\) up to a constant in the exponent.
A famous question of Erdés asks for plane integral point sets with no \(3\) points on a line and no \(4\) points on a circle. Here, we talk of point sets in general position and denote the corresponding minimum diameter by \(d(2,n)\). Recently \(d(2, 7) = 22270\) could be determined via an exhaustive search.

In this paper, we study invariant sequences by umbral method, and give some identities which are similar with the identities of Bernoulli numbers.

In this paper, we consider the total domination number, the restrained domination number, the total restrained domination number and the connected domination number of lexicographic product graphs.

In this paper, we obtain the numbers of embeddings of wheel graphs on some orientable and nonorientable surfaces of small genera, mainly on torus, double torus, and nonorientable surfaces of genus \(1, 2, 3\), and \(4\). These are the first results for embeddings of wheel graphs on nonorientable surfaces as known up to now.

An \((a, d)\)-edge-antimagic total labeling for a graph \(G(V, E)\) is an injective mapping \(f\) from \(V \cup E\) onto the set \(\{1, 2, \ldots, |V| + |E|\}\) such that the set \(\{f(v) + \sum f(uv) \mid uv \in E\}\), where \(v\) ranges over all of \(V\), is \(\{a, a+d, a+2d, \ldots, a+(|V|-1)d\}\). Simanjuntak et al conjecture:1. \(C_{2n}\) has a \((2n + 3, 4)\)- or a \((2n + 4, 4)\)-edge-antimagic total labeling;
2. cycles have no \((a, d)\)-edge-antimagic total labelings with \(d > 5\).In this paper, these conjectures are shown to be true.

This article discusses the geometricity of the direct sum, direct product and lexicographic products of two lattices, and compute their characteristic polynomials and classify their geometricity.

This paper introduces the concepts of a \({supergraph}\) and \({graphical\; complexity}\) of a permutation group, intended as a tool for investigating the structure of concrete permutation groups. Basic results are established and some research problems suggested.

We given a two parameter generalization of identities of Carlitzand Gould involving products of binomial coefficients. The generalization involves Jacobi polynomials.

Consider a connected undirected graph \(G = (V, E)\) and an integer \(r \geq 1\). For any vertex \(v \in V\), let \(B_r(v)\) denote the ball of radius \(r\) centered at \(v\), i.e., the set of all vertices linked to \(v\) by a path of at most \(r\) edges. If for all vertices \(v \in V\), the sets \(B_r(v)\) are different, then we say that \(G\) is \(r\)-twin-free.

Studies have been made, e.g., on the number of edges or the minimum degree in one-twin-free graphs. We extend these investigations and in particular we determine the exact size of the largest clique in a connected \(r\)-twin-free graph.

Let \(D\) be a strongly connected digraph with order at least two. Let \(M(D)\) denote the middle digraph of \(D\), and let \(\kappa(D)\) and \(\lambda(D)\) denote the connectivity and arc-connectivity of \(D\), respectively. In this paper, we study super-arc-connected and super-connected middle digraphs and the spectrum of middle digraphs.

For a connected graph \(G\) of order \(p \geq 2\), a set \(S \subseteq V(G)\) is an \(x\)-geodominating set of \(G\) if each vertex \(v \in V(G)\) lies on an \(x\)-geodesic for some element \(y \in S\). The minimum cardinality of an \(x\)-geodominating set of \(G\) is defined as the \(\alpha\)-geodomination number of \(G\), denoted by \(g_x(G)\) or simply \(g_x(G)\). An \(x\)-geodominating set of cardinality \(g_x(G)\) is called a \(g_x(G)\)-set. A connected graph of order \(p\) with vertex geodomination numbers either \(p – 1\) or \(p – 2\) for every vertex is characterized. It is shown that there is no graph of order \(p\) with vertex geodomination number \(p – 2\) for every vertex. Also, for an even number \(p\) and an odd number \(n\) with \(1 \leq n \leq p – 1\), there exists a connected graph \(G\) of order \(p\) and \(g_x(G) = n\) for every vertex \(x \in G\), and for an odd number \(p\) and an even number \(n\) with \(1 \leq n \leq p – 1\), there exists a connected graph \(G\) of order \(p\) and \(g_x(G) = n\) for every vertex \(x \in G\). It is shown that for any integer \(n > 2\), there exists a connected regular as well as a non-regular graph \(G\) with \(g_x(G) = n\) for every vertex \(x \in G\). For positive integers \(r, d\) and \(n \geq 2\) with \(r \leq d \leq 2r\), there exists a connected graph \(G\) of radius \(r\), diameter \(d\) and \(g_x(G) = n\) for every vertex \(x \in G\). Also, for integers \(p, d\) and \(n\) with \(3 \leq d \leq p – 1, 1 \leq n \leq p – 1\) and \(p – d – n + 1 \geq 0\), there exists a graph \(G\) of order \(p\), diameter \(d\) and \(g_x(G) = n\) for some vertex \(x \in G\).

A graph is called \emph{biclaw-free} if it has no biclaw as an induced subgraph. Lai and Yao [Discrete Math., \(307 (2007) 1217\)] conjectured that every \(2\)-connected biclaw-free graph \(G\) with \(\delta(G) \geq 4\) has a spanning eulerian subgraph \(H\) with maximum degree \(\Delta(H) \leq 4\). In this note, the conjecture is answered in the negative.

Let \(G\) be a graph of order \(n\) and size \(m\). A \(\gamma\)-labeling of \(G\) is a one-to-one function \(f: V(G) \to \{0, 1, 2, \ldots, m\}\) that induces a labeling \(f’: E(G) \to \{1, 2, \ldots, m\}\) of the edges of \(G\) defined by \(f'(e) = |f(u) – f(v)|\) for each edge \(e = uv\) of \(G\). The value of a \(\gamma\)-labeling \(f\) is defined as

\[val(f) = \sum\limits_{e \in E(G)} f'(e).\]

The \(\gamma\)-spectrum of a graph \(G\) is defined as

\[spec(G) = \{val(f): f \text{ is a \(\gamma\)-labeling of } G\}.\]

The \(\gamma\)-spectra of paths, cycles, and complete graphs are determined.

An \((a, d)\)-edge-antimagic total labeling on a \((p, q)\)-graph \(G\) is a one-to-one map \(f\) from \(V(G) \cup E(G)\) onto the integers \(1, 2, \ldots, p+q\) with the property that the edge-weights, \(w(uv) = f(u) + f(v) + f(uv)\) where \(uv \in E(G)\), form an arithmetic progression starting from \(a\) and having common difference \(d\). Such a labeling is called \emph{super} if the smallest possible labels appear on the vertices. In this paper, we investigate the existence of super \((a, d)\)-edge-antimagic total labeling of the disjoint union of multiple copies of the complete tripartite graph and the disjoint union of stars.

Given a configuration of pebbles on the vertices of a graph \(G\), a pebbling move consists of taking two pebbles off a vertex \(v\) and putting one of them back on a vertex adjacent to \(v\). A graph is called \({pebbleable}\) if for each vertex \(v\) there is a sequence of pebbling moves that would place at least one pebble on \(v\). The \({pebbling\;number}\) of a graph \(G\), is the smallest integer \(m\) such that \(G\) is pebbleable for every configuration of \(m\) pebbles on \(G\). A graph \(G\) is said to be class \(0\) if the pebbling number of \(G\) is equal to the number of vertices in \(G\). We prove that \(Bi-wheels\), a class of diameter three graphs, are class \(0\).

In this paper, we study the flexibility of embeddings of circular graphs \(C(2n,2)\), \(n \geq 3\) on the projective plane. The numbers of (non-equivalent) embeddings of \(C(2n, 2)\) on the projective plane are obtained, and by describing structures of these embeddings, the numbers of (non-equivalent) weak embeddings and strong embeddings of \(C(2n, 2)\) on the projective plane are also obtained.

In \([4]\), Elizalde and Pak gave a bijection \(\Theta: S_n(321) \to S_n(132)\) that commutes with the operation of taking inverses and preserves the numbers of fixed points and excedances for every \(\Gamma \in S_n(321)\). In \([1]\) it was shown that another bijection \(\Gamma: S_n(321) \to S_n(132)\) introduced by Robertson in \([7]\) has these same properties, and in \([2]\) a pictorial reformulation of \(\Gamma\) was given that made it clearer why \(\Gamma\) has these properties. Our purpose here is to give a similar pictorial reformulation of \(\Theta\), from which it follows that, although the original definitions of \(\Theta\) and \(\Gamma\) make them appear quite different, these two bijections are in fact related to each other in a very simple way, by using inversion, reversal, and complementation.

Gyarfas conjectured that for a given forest \(F\), there exists an integer function \(f(F,w(G))\) such that \(\chi(G) \leq f(F,w(G))\) for any \(F\)-free graph \(G\), where \(\chi(G)\) and \(w(G)\) are respectively, the chromatic number and the clique number of G. Let G be a \(C_5\)-free graph and \(k\) be a positive integer. We show that if \(G\) is \((kP_1, + P_2)\)-free for \(k \geq 2\), then \(\chi(G) \leq 2w^{k-1} \sqrt{w}\); if \(G\) is \((kP_1, + P_3)\)-free for \(k \geq 1\), then \(\chi(G) \leq w^k \sqrt{w}\). A graph \(G\) is \(k\)-divisible if for each induced subgraph \(H\) of \(G\) with at least one edge, there is a partition of the vertex set of \(H\) into \(k\) sets \({V_1,… , V_k}\) such that no \(V_i\); contains a clique of size \(w(G)\). We show that a \((2P_1+P_2)\)-free and \(C_5\)-free graph is \(2\)-divisible.

The concept of the sum graph and integral sum graph were introduced by F. Harary. Let \(\mathbb{N}\) denote the set of all positive integers. The sum graph \(G^+(S)\) of a finite subset \(S \subset {N}\) is the graph \((S, E)\) with \(uv \in E\) if and only if \(u+v \in S\). A simple graph \(G\) is said to be a sum graph if it is isomorphic to a sum graph of some \(S \subset {N}\). The sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices which when added to \(G\) result in a sum graph. Let \(\mathbb{Z}\) denote the set of all integers. The integral sum graph \(G^+(S)\) of a finite subset \(S \subset {Z}\) is the graph \((S, E)\) with \(uv \in E\) if and only if \(u+v \in S\). A simple graph \(G\) is said to be an integral sum graph if it is isomorphic to an integral sum graph of some \(S \subset {Z}\). The integral sum number \(\zeta(G)\) of \(G\) is the smallest number of isolated vertices which when added to \(G\) result in an integral sum graph. In this paper, we investigate and determine the sum number and the integral sum number of the graph \(K_n \setminus E(C_{n-1})\). The results are presented as follows:\(\zeta(K_n \setminus (C_{n-1})) = \begin{cases}
0, & n = 4,5,6,7 \\
2n-7, & n \geq 8
\end{cases}\)
and
\(\sigma(K_n \setminus E(C_{n-1})) = \begin{cases}
1, & n = 4 \\
2, & n = 5\\
5, & n = 5\\
7, & n = 7\\
2n-7, & n \geq 8
\end{cases}\)

The topic is the hat problem, in which each of \(n\) players is randomly fitted with a blue or red hat. Then, everybody can try to guess simultaneously their own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses their hat color correctly, and no one guesses their hat color wrong; otherwise, the team loses. The aim is to maximize the probability of winning. In this version, every player can see everybody excluding themselves. We consider such a problem on a graph, where vertices correspond to players, and a player can see each player to whom they are connected by an edge. The solution of the hat problem on a graph is known for trees and for the cycle \(C_4\). We solve the problem on cycles with at least nine vertices.

Let \(D(G)\) be the Davenport constant of a finite abelian group \(G\), defined as the smallest positive integer \(d\) such that every
sequence of \(d\) elements in \(G\) contains a nonempty subsequence with sum zero the identity of \(G\). In this short note, we use group rings as a tool to characterize the Davenport constant.

It is proved that if \(G\) is a \(K_{2,3}\)-minor-free graph with maximum degree \(\Delta\), then \(\Delta+ 1 \leq \chi(G^2) \leq ch(G^2) \leq \Delta+2\) if \(\Delta \geq 3\), and \(ch(G^2) = \chi(G^2) = \Delta+1\) if \(\Delta \geq 6\). All inequalities here are sharp,even for outerplanar graphs.

Here, we determine all graphs of order less than \(7\) which are not product cordial.Also, we give some families of graphs which are product cordial.

A path in an edge-colored graph \(G\), where adjacent edges may be colored the same, is called a rainbow path if no two edges of the path are colored the same. For a \(k\)-connected graph \(G\) and an integer \(k\) with \(1 \leq k \leq \kappa\), the rainbow \(k\)-connectivity \(rc_k(G)\) of \(G\) is defined as the minimum integer \(j\) for which there exists a \(j\)-edge-coloring of \(G\) such that any two distinct vertices of \(G\) are connected by \(k\) internally disjoint rainbow paths. Denote by \(K_{r,r}\) an \(r\)-regular complete bipartite graph. Chartrand et al. in in “G. Chartrand, G.L. Johns, K.A.McKeon, P. Zhang, The rainbow connectivity of a graph, Networks \(54(2009), 75-81”\) left an open question of determining an integer \(g(k)\) for which the rainbow \(k\)-connectivity of \(K_{r,r}\) is \(3\) for every integer \(r \geq g(k)\). This short note is to solve this question by showing that \(rc_k(K_{r,r}) = 3\) for every integer \(r \geq 2k\lceil\frac{k}{2}\rceil\), where \(k \geq 2\) is a positive integer.

Let \(G\) be a connected graph with edge set \(E(G)\). The Balaban index of \(G\) is defined as \(J(G) = \frac{m}{\mu+1} \sum_{uv \in E(G)} ({D_uD_v})^{-\frac{1}{2}}\) where \(m = |E(G)|\), and \(\mu\) is the cyclomatic number of \(G\), \(D_u\) is the sum of distances between vertex \(u\) and all other vertices of \(G\). We determine \(n\)-vertex trees with the first several largest and smallest Balaban indices.

For a graph \(G = (V, E)\), \(X \subseteq V\) is a global dominating set if \(X\) dominates both \(G\) and the complement graph \(\bar{G}\). A set \(X \subseteq V\) is a packing if its pairwise members are distance at least \(3\) apart. The minimum number of vertices in any global dominating set is \(\gamma_g(G)\), and the maximum number in any packing is \(\rho(G)\). We establish relationships between these and other graphical invariants, and characterize graphs for which \(\rho(G) = \rho(\bar{G})\). Except for the two self-complementary graphs on \(5\) vertices and when \(G\) or \(\bar{G}\) has isolated vertices, we show \(\gamma_g(G) \leq \lfloor n/2 \rfloor\), where \(n = |V|\).

The inverse degree \(r(G)\) of a finite graph \(G = (V, E)\) is defined by \(r(G) = \sum_{v\in V} \frac{1}{deg(v)}\) where \(deg(v)\) is the degree of \(v\) in \(G\). Erdős \(et\) \(al\). proved that, if \(G\) is a connected graph of order \(n\), then the diameter of \(G\) is less than \((6r(G) + \sigma(1))\frac{\log n}{\log \log n}\). Dankelmann et al. improved this bound by a factor of approximately \(2\). We give the sharp upper bounds for trees and unicyclic graphs, which improves the above upper bounds.

Let \(\gamma_c(G)\) be the connected domination number of \(G\) and \(\gamma_{tr}(G)\) be the tree domination number of \(G\). In this paper, we study the generalized Petersen graphs \(P(n,k)\), prove \(\gamma_c(P(n, k)) = \gamma_{tr}(P(n, k))\) and show their exact values for \(k = 1, 2, \ldots, \lfloor n/2 \rfloor\).

Given a parity-check matrix \({H}\) with \(n\) columns, an \(\ell\)-subset \(T\) of \(\{1,2,\ldots,n\}\) is called a stopping set of size \(\ell\) for \({H}\) if the \(\ell\)-column submatrix of \({H}\) consisting of columns with coordinate indexes in \(T\) has no row of Hamming weight one. The size of the smallest non-empty stopping sets for \({H}\) is called the stopping distance of \({H}\).

In this paper, the stopping distance of \({H}_{m}(2t+1)\), parity-check matrices representing binary \(t\)-error-correcting \(BCH\) codes, is addressed. It is shown that if \(m\) is even then the stopping distance of this matrix is three. We conjecture that this property holds for all integers \(m \geq 3\).

For the sequence satisfying the recurrence relation of the second order, we establish a general summation theorem on the infinite series of the reciprocal product of its two consecutive terms. As examples, several infinite series identities are obtained on Fibonacci and Lucas numbers, hyperbolic sine and cosine functions, as well as the solutions of Pell equation.

The directed \(\overrightarrow{P}_k\)-graph of a digraph \(D\) is obtained by representing the directed paths on \(k\) vertices of \(D\) by vertices. Two such vertices are joined by an arc whenever the corresponding directed paths in \(D\) form a directed path on \(k+1\) vertices or a directed cycle on \(k\) vertices in \(D\). In this paper, we give a necessary and sufficient condition for two digraphs with isomorphic \(\overrightarrow{P}_3\)-graphs. This improves a previous result, where some additional conditions were imposed.

In this paper, we study quaternary quasi-cyclic \((QC)\) codes with even length components. We determine the structure of one generator quaternary \(QC\) codes whose cyclic components have even length. By making use of their structure, we establish the size of these codes and give a lower bound for minimum distance. We present some examples of codes from this family whose Gray images have the same Hamming distances as the Hamming distances of the best known binary linear codes with the given parameters. In addition, we obtain a quaternary \(QC\) code that leads to a new binary non-linear code that has parameters \((96, 2^{26}, 28)\).

Let \(G\) be a simple graph, and let \(p\) be a positive integer. A subset \(D \subseteq V(G)\) is a \(p\)-dominating set of the graph \(G\), if every vertex \(v \in V(G) – D\) is adjacent to at least \(p\) vertices in \(D\). The \(p\)-domination number \(\gamma_p(G)\) is the minimum cardinality among the \(p\)-dominating sets of \(G\). A subset \(I \subseteq V(G)\) is an independent dominating set of \(G\) if no two vertices in \(I\) are adjacent and if \(I\) is a dominating set in \(G\). The minimum cardinality of an independent dominating set of \(G\) is called independence domination number \(i(G)\).

In this paper, we show that every block-cactus graph \(G\) satisfies the inequality \(\gamma_2(G) \geq i(G)\) and if \(G\) has a block different from the cycle \(C_3\), then \(\gamma_2(G) \geq i(G) + 1\). In addition, we characterize all block-cactus graphs \(G\) with \(\gamma_2(G) = i(G)\) and all trees \(T\) with \(\gamma_2(T) = i(T) + 1\).

We show that if \(G\) has an odd graceful labeling \(f\) such that \(\max\{f(x): f(x) \text{ is even}, x \in A\} < \min\{f(x): f(x) \text{ is odd}, x \in B\}\), then \(G\) is an o-graph, and if \(G\) is an a-graph, then \(G \odot K_{n}\) is odd graceful for all \(w \geq 1\). Also, we show that if \(G_{1}\) is an a-graph and \(G_{2}\) is an odd graceful, then \(G_{1} \cup G_{2}\) is odd graceful. Finally, we show that some families of graphs are a-graphs and odd graceful.

Let \(K_{m} – H\) be the graph obtained from \(K_{m}\) by removing the edges set \(E(H)\) of \(H\) where \(H\) is a subgraph of \(K_{m}\). In this paper, we characterize the potentially \(K_{5} – P_{3}\), \(K_{5} – A_{3}\), \(K_{5} – K_{3}\) and \(K_{5} – K_{1,3}\)-graphic sequences where \(A_{3}\) is \(P_{2}\cup K_{2}\). Moreover, we also characterize the potentially \(K_{5} – 2K_{2}\)-graphic sequences where \(pK_2\) is the matching consisted of \(p\) edges.

Let \(G = (V, E)\) be a simple connected graph, where \(d_v\) is the degree of vertex \(v\). The zeroth-order Randić index of \(G\) is defined as \(R^0_n(G) = \sum_{v \in V} d_v^\alpha\), where \(\alpha\) is an arbitrary real number. Let \(G^*\) be the thorn graph of \(G\) by attaching \(d_G(v_i)\) new pendent edges to each vertex \(v_i\) (\(1 \leq i \leq n\)) of \(G\). In this paper, we investigate the zeroth-order general Randić index of a class thorn tree and determine the extremal zeroth-order general Randić index of the thorn graphs \(G^*(n,m)\).

Let \(X\) denote a set with \(q\) elements. Suppose \(\mathcal{L}(n, q)\) denotes the set \(X^n\) (resp. \(X^n \cup \{\Delta\}\)) whenever \(q = 2\) (resp. \(q \geq 3\)). For any two elements \(\alpha = (\alpha_1, \ldots, \alpha_n)\) and \(\beta = (\beta_1, \ldots, \beta_n) \in \mathcal{L}(n, q)\), define \(\alpha \leq \beta\) if and only if \(\beta = \Delta\) or \(\alpha_i = \beta_i\) whenever \(\alpha_i \neq 0\) for \(1 \leq i \leq n\). Then \(\mathcal{L}(n, q)\) is a lattice, denoted by \(\mathcal{L}_\bigcirc(n, q)\). Reversing the above partial order, we obtain the dual of \(\mathcal{L}_\bigcirc(n, q)\), denoted by \(\mathcal{L}_R(n, q)\). This paper discusses their geometricity, and computes their characteristic polynomials, determines their full automorphism groups. Moreover, we construct a family of quasi-strongly regular graphs from the lattice \(\mathcal{L}_\bigcirc(n, q)\).

A minimal separator of a graph is an inclusion-minimal set of vertices whose removal disconnects some pair of vertices. We introduce a new notion of minimal weak separator of a graph, whose removal merely increases the distance between some pair of vertices.

The minimal separators of a chordal graph \(G\) have been identified with the edges of the clique graph of \(G\) that are in some clique tree, while we show that the minimal weak separators can be identified with the edges that are in no clique tree. We also show that the minimal weak separators of a chordal graph \(G\) can be identified with pairs of minimal separators that have nonempty intersection without either containing the other—in other words, the minimal weak separators can be identified with the edges of the overlap graph of the minimal separators of \(G\).

A monitor is a computer in the network which is able to detect a fault computer among its neighbors. There are two stages of monitoring fault computer:(1) Sensing a fault among its neighbors and (2) Locating the fault computer.
A sensitive computer network requires double layer monitoring system where monitors are monitored. This problem is modeled using the graph theory concept of dominating set. In graph theory, there are two variations of domination concepts which represent double layer monitoring system.One concept is locating-domination and the other is liar domination.

It has been recently demonstrated that circulant network is a suitable topology for the design of On-Chip Multiprocessors and has several advantages over torus and hypercube from the perspectives of VLSI design. In this paper, we study both locating-domination and liar domination in circulant networks. In addition to characterization of locating-dominating set and liar dominating set of circulant networks, sharp lower and upper bounds of locating-dominating set and liar dominating set of circulant networks are presented.

We obtain some new examples of weakly distance-regular digraphs. Moreover, a class of commutative weakly distance-regular
digraphs of valency \(4\) and girth \(2\) is characterized.

A graph \(G\) is called \(H\)-equicoverable if every minimal \(H\)-covering in \(G\) is also a minimum \(H\)-covering in \(G\). In this paper, we give the characterization of connected \(M_2\)-equicoverable graphs with circumference at most \(5\).

In this paper, we investigate the existence of \(2\)-\((v,8,1)\) designs admitting a block-transitive automorphism group \(G \leq \mathrm{ATL}(1,q)\). Using Weil’s theorem on character sums, the following theorem is proved:If a prime power \(q\) is large enough and \(q \equiv 57 \pmod{112}\), then there is always a \(2-(v,8,1)\) design which has a block-transitive, but non flag-transitive automorphism group \(G.\)