Let \(G\) be a graph with a vertex coloring. A colorful path is a path with \(\chi(G)\) vertices, in which the vertices have different colors. A colorful path starting at vertex \(v\) is a colorful \(v\)-path. We show that for every graph \(G\) and given vertex \(v\) of \(G\), there exists a proper vertex coloring of \(G\) with a colorful path starting at \(v\). Let \(G\) be a connected graph with maximum degree \(\Delta(G)\) and \(|V(G)| \geq 2\). We prove that there exists a proper \((\chi(G) + \Delta(G) – 1)\)-coloring of \(G\) such that for every \(v \in V(G)\), there is a colorful \(v\)-path.

Let \(\mathcal{B}(n,d)\) be the set of bicyclic graphs with both \(n\) vertices and diameter \(d\), and let \(\theta^*\) consist of three paths \(u_0w_1v_0\), \(u_0w_2v_0\), and \(u_0w_3v_0\). For four nonnegative integers \(n,d,k,j\) satisfying \(n \geq d+3\), \(d=k+j+2\), we let \(B(n,d;k,j)\) denote the bicyclic graph obtained from \(\theta^*\) by attaching a path of length \(k\) to \(u_0\), attaching a path of length \(j\) to vertex \(v_0\) and \(n-d-3\) pendant edges to \(w_0\), and let \(\mathcal{B}(n,d;k,j) = \{B(n,d;k,j) \mid k+j \geq 1\}\). In this paper, the extremal graphs with the minimal least eigenvalue among all graphs in \(\mathcal{B}(n,d;k,j)\) are well characterized, and some structural characterizations about the extremal graphs with the minimal least eigenvalue among all graphs in \(\mathcal{B}(n,d)\) are presented as well.

If \(G = (V, E)\) is a simple connected graph and \(a, b \in V\), then a shortest \((a – b)\) path is called an \((a – b)\)-geodesic. A set \(X \subseteq V\) is called weakly convex in \(G\) if for every two vertices \(a, b \in X\) there exists an \((a – b)\)-geodesic whose all vertices belong to \(X\). A set \(X\) is convex in \(G\) if for every \(a, b \in X\) all vertices from every \((a – b)\)-geodesic belong to \(X\). The weakly convex domination number of a graph \(G\) is the minimum cardinality of a weakly convex dominating set in \(G\), while the convex domination number of a graph \(G\) is the minimum cardinality of a convex dominating set in \(G\). In this paper, we consider weakly convex and convex domination numbers of Cartesian products, joins, and coronas of some classes of graphs.

Using a new way to label edges in a bicoloured ordered tree,we introduce a bijection between bicoloured ordered trees and non-nesting partitions. Consequently, enumerative results of non-nesting partitions are derived. Together with another bijection given before, we obtain a bijection between non-nesting partitions and non-crossing partitions specified with four parameters.

Lee and Wei defined super vertex-graceful labeling in 2006. In this paper, the generalized Butterfly Graph \(B_{n}^t\) and \(C_n^{(t)}\) graph are discussed. The generalized butterfly Graph \(B_{n}^t\) is super vertex-graceful when \(t\) (\(t > 0\)) is even, \(B_{n}^0\) is super vertex-graceful when \(n \equiv 0, 3 \pmod{4}\); For \(C_3^{(t)}\), there are: \(C_3^{(t)}\) is super vertex-graceful if and only if \(t = 1, 2, 3, 5, 7\). Moreover, we propose two conjectures on super vertex-graceful labeling.

An adjacent vertex distinguishing edge coloring, or an avd-coloring, of a simple graph \(G\) is a proper edge coloring of \(G\) such that for any two adjacent and distinct vertices \(u\) and \(v\) in \(G\), the set of colors assigned to the edges incident to \(u\) differs from the set of colors assigned to the edges incident to \(v\). In this paper, we prove that graphs with maximum degree \(3\) and with no isolated edges partly satisfy the adjacent vertex distinguishing edge coloring conjecture.

An \(L(2,1)\)-labeling of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all nonnegative integers such that \(|f(x) – f(y)| \geq 2\) if \(d(x,y) = 1\) and \(|f(x) – f(y)| \geq 1\) if \(d(x,y) = 2\), where \(d(x,y)\) denotes the distance between vertices \(x\) and \(y\) in \(G\). The \(L(2,1)\)-labeling number \(\lambda(G)\) of \(G\) is the smallest number \(k\) such that \(G\) has an \(L(2,1)\)-labeling with \(\max\{f(v) : v \in V(G)\} = k\). We consider Cartesian sums of graphs and derive, both, lower and upper bounds for the \(L(2,1)\)-labeling number of this class of graphs; we use two approaches to derive the upper bounds for the \(L(2,1)\)-labeling number and both approaches improve previously known upper bounds. We also present several approximation algorithms for computing \(L(2,1)\)-labelings for Cartesian sum graphs.

Assume that \(G = (V, E)\) is an undirected graph with vertex set \(V\) and edge set \(E\). The ball \(B_r(v)\) denotes the vertices within graphical distance \(r\) from \(v\). A subset \(C \subseteq V\) is called an \(r\)-locating-dominating code if the sets \(I_r(v) = B_r(v) \cap C\) are distinct and non-empty for all \(v \in V \setminus C\). A code \(C\) is an \(r\)-identifying code if the sets \(I_r(v) = B_r(v) \cap C\) are distinct and non-empty for all vertices \(v \in V\). We study \(r\)-locating-dominating codes in the infinite king grid and, in particular, show that there is an \(r\)-locating-dominating code such that every \(r\)-identifying code has larger density. The infinite king grid is the graph with vertex set \(\mathbb{Z}^2\) and edge set \(\{(x_1, y_1), (x_2, y_2) \mid |x_1 – x_2| \leq 1, |y_1 – y_2| \leq 1, (x_1, y_1) \neq (x_2, y_2)\}\).

An antimagic labeling of a graph with \(n\) vertices and \(m\) edges is a bijection from the set of edges to the integers \(1, 2, \ldots, m\) such that all \(n\) vertex sums are pairwise distinct. For a cycle \(C_n\) of length \(n\), the \(k\)-th power of \(C_n\), denoted by \(C_n^k\), is the supergraph formed by adding an edge between all pairs of vertices of \(C_n\) with distance at most \(k\). Antimagic labelings for \(C_n^k\) are given where \(k = 2, 3, 4\).

In 1990, Kostochka and Sidorenko proposed studying the smallest number of list-colorings of a graph \(G\) among all assignments of lists of a given size \(n\) to its vertices. We say a graph \(G\) is \(n\)-monophilic if this number is minimized when identical \(n\)-color lists are assigned to all vertices of \(G\). Kostochka and Sidorenko observed that all chordal graphs are \(n\)-monophilic for all \(n\). Donner (1992) showed that every graph is \(n\)-monophilic for all sufficiently large \(n\). We prove that all cycles are \(n\)-monophilic for all \(n\); we give a complete characterization of \(2\)-monophilic graphs (which turns out to be similar to the characterization of \(2\)-choosable graphs given by Erdős, Rubin, and Taylor in 1980); and for every \(n\) we construct a graph that is \(n\)-choosable but not \(n\)-monophilic.

An adjacent vertex distinguishing total coloring of a graph \(G\) is a proper total coloring of \(G\) such that no two adjacent vertices are incident to the same set of colors. The minimum number of colors needed for such a coloring is denoted by \(\chi_{at}(G)\). In this note, we prove that \(\chi_{at}(G) = 5\) for some cubic graphs.

In this paper, a generalized notion of the fixed point property,namely the \(n\)-fixed point property, for posets is discussed. The \(n\)-fixed point property is proved to be equivalent to the fixed point property in lattices. Further, it is shown that a poset of finite width has the \(n\)-fixed point property for some natural number \(n\) if and only if every maximal chain in it is a complete lattice.

A graph is said to be equitably \(k\)-colorable if the vertex set \(V(G)\) can be partitioned into \(k\) independent subsets \(V_1, V_2, \ldots, V_k\) such that \(||V_i| – |V_j|| \leq 1\) (\(1 \leq i, j \leq k\)). A graph \(G\) is equitably \(k\)-choosable if, for any given \(k\)-uniform list assignment \(L\), \(G\) is \(L\)-colorable and each color appears on at most \(\lceil \frac{|V(G)|}{k} \rceil\) vertices. In this paper, we prove that if \(G\) is a graph such that \(\mathrm{mad}(G) \leq 3\), then \(G\) is equitably \(k\)-colorable and equitably \(k\)-choosable where \(k \geq \max\{\Delta(G), 5\}\).

For a vertex \(v\) of a graph \(G\), the unlabeled subgraph \(G-v\) is called a card of \(G\). We prove that the number of isolated vertices and the number of components of an \(n\)-vertex graph \(G\) can be determined from any collection of \(n-2\) of its cards for \(n \geq 10\). It is also proved that if two graphs of order \(n \geq 6\) have \(n-2\) cards in common, then the number of edges in them differs by at most one.

The Hosoya index \(z(G)\) of a graph \(G\) is defined as the total number of matchings of \(G\), and the Merrifield-Simmons index \(i(G)\) of a graph \(G\) is defined as the total number of independent sets of \(G\). Although there are many known results on these two indices, there exist few on a given class of graphs with perfect matchings. In this paper, we first introduce two new strengthened transformations. Then we characterize the extremal unicyclic graphs with perfect matching which have minimal, second minimal Hosoya index, and maximal, second maximal Merrifield-Simmons index, respectively.

The aim of this paper is to introduce the notions of \(f\)-derivation and symmetric bi-derivation in \(c\)-subtraction algebras and to study some properties of these derivations.

A book-embedding of a graph \(G\) consists of placing the vertices of \(G\) on a spine and assigning edges of the graph to pages so that edges assigned to the same page without crossing. In this paper,we propose schemes to embed the connected triple-loop networks with even cardinality in books, then we give upper bounds of page number of some multi-loop networks.

Determining the size of a maximum independent set of a graph \(G\), denoted by \(\alpha(G)\), is an NP-hard problem. Therefore, many attempts are made to find upper and lower bounds, or exact values of \(\alpha(G)\) for special classes of graphs. This paper is aimed towards studying this problem for the class of generalized Petersen graphs. We find new upper and lower bounds and some exact values for \(\alpha(P(n,k))\). With a computer program, we have obtained exact values for each \(n 2k\). We prove this conjecture for some cases. In particular, we show that if \(n > 3k\), the conjecture is valid. We checked the conjecture with our table for \(n < 78\) and found no inconsistency. Finally, we show that for every fixed \(k\), \(\alpha(P(n,k))\) can be computed using an algorithm with running time \(O(n)\).

In this paper we give the solutions of finding maximum packings and minimum coverings of \(\lambda\)-fold complete symmetric digraphs with \(6\)-circuits.

In recent researches on a discriminant for polynomials, I faced a recursive (combinatorial) sequence \(\lambda_{n,m}\) whose first four terms and identities are \(\lambda_{0,m} := \binom{m}{0}\), \(\lambda_{1,m} := \binom{m}{1}=\binom{m}{m-1}\), \(\lambda_{2,m} := {\binom{m}{2}}^2 – \binom{m}{2}=\binom{m+1}{m-1}\), and \(\lambda_{3,m} = {\binom{m}{1}}^3 – 2\binom{m}{1}\binom{m}{2} + \binom{m}{3}=\binom{m+2}{m-1}\). In this paper, I introduce this sequence, prove an identity concerning it, and leave a problem and a conjecture regarding its properties.

Let \(\mu_1, \mu_2, \ldots, \mu_n\) be the eigenvalues of the sum-connectivity matrix of a graph \(G\). The sum-connectivity spectral radius of \(G\) is the largest eigenvalue of its sum-connectivity matrix, and the sum-connectivity Estrada index of \(G\) is defined as \(\mathrm{SEE}(G) = \sum_{i=1}^{n} e^{\mu_i}\). In this paper, we obtain some results about the sum-connectivity spectral radius of graphs. In addition, we give some upper and lower bounds on the sum-connectivity Estrada index of graph \(G\), as well as some relations between \(\mathrm{SEE}\) and sum-connectivity energy. Moreover, we characterize that the star has maximum sum-connectivity Estrada index among trees on \(n\) vertices.

Let \(G(n;\theta_{2k+1})\) denote the class of non-bipartite graphs on \(n\) vertices containing no \(\theta_{2k+1}\)-graph and let \(f(n; \theta_{2k+1}) = \max\{\varepsilon(G) : G \in \mathcal{G}(n;\theta_{2k+1})\}\). In this paper, we determine \(f(n; 0_5)\), by proving that for \(n \geq 11\), \(f(n; 0_5) \leq \lfloor\frac{(n-1)^2}{4}\rfloor + 1\). Further, the bound is best possible. Our result confirms the validity of the conjecture made in [1], “Some extremal problems in graph theory”, Ph.D. thesis, Curtin University of Technology, Australia (2007).

Let \(G\) be a cactus, where all blocks of \(G\) are either edges or cycles. Denote \(\mathcal{G}(n,r)\) the set of cactuses of order \(n\) and with \(r\) cycles. In this paper, we present a unified approach to the extremal cactuses for the Schultz and the modified Schultz indices.

In this paper, I study the Eulerian numbers \((A(m,k))_{k=1}^{m}\) and prove the relationship between \(\sum_{i=1}^{n}{i^m}\) and \((A(m,k))_{k=1}^{m}\), to be \(\sum_{i=1}^{n}{i^m} = \sum_{k=1}^m A(m,k)\binom{m+k}{m+1}\).

An \((s, t)\)-spread in a finite vector space \(V = V(n, q)\) is a collection \(\mathcal{F}\) of \(t\)-dimensional subspaces of \(V\) with the property that every \(s\)-dimensional subspace of \(V\) is contained in exactly one member of \(F\). It is remarkable that no \((s, t)\)-spreads have been found yet, except in the case \(s = 1\).
In this note, the concept of an \(\alpha\)-point to a \((2,3)\)-spread \(\mathcal{F}\) in \(V = V(7,2)\) is introduced. A classical result of Thomas, applied to the vector space \(V\), states that all points of \(V\) cannot be \(\alpha\)-points to a given \((2,3)\)-spread \(\mathcal{F}\) in \(V\). In this note, we strengthen this result by proving that every \(6\)-dimensional subspace of \(V\) must contain at least one point that is not an \(\alpha\)-point to a given \((2, 3)\)-spread.

We construct explicitly the automorphism group of the folded hypercube \(FQ_n\) of dimension \(n > 3\), as a semidirect product of \(N\) by \(M\), where \(N\) is isomorphic to the Abelian group \(\mathbb{Z}_2^{n}\), and \(M\) is isomorphic to \(\mathrm{Sym}(n+1)\), the symmetric group of degree \(n+1\). Then, we will show that the folded hypercube \(FQ_n\) is a symmetric graph.

The Merrifield-Simmons index \(\sigma(G)\) of a graph \(G\) is defined as the number of subsets of the vertex set, in which any two vertices are non-adjacent, i.e., the number of independent vertex sets of \(G\). A tree is called an \(r\)-leaf tree if it contains \(r\) vertices with degree one. In this paper, we obtain the smallest Merrifield-Simmons index among all trees with \(n\) vertices and exactly six leaves, and characterize the corresponding extremal graph.

A family \(\mathcal{G}\) of connected graphs is a family with constant metric dimension if \(\dim(G)\) is finite and does not depend upon the choice of \(G\) in \(\mathcal{G}\). The metric dimension of some classes of plane graphs has been determined in \([2], [3],[ 4], [9], [10], [14], [22]\). In this paper, we extend this study by considering some classes of plane graphs which are rotationally-symmetric. It is natural to ask for the characterization of classes of rotationally-symmetric plane graphs with constant metric dimension.

is almost locally connected if \(B(G)\) is an independent set and for any \(x \in B(G)\), there is a vertex \(y\) in \(V(G) \setminus \{x\}\) such that \(N(x) \cup \{y\}\) induces a connected subgraph of \(G\), where \(B(G)\) denotes the set of vertices of \(G\) that are not locally connected. In this paper, we prove that an almost locally connected claw-free graph on at least \(4\) vertices is Hamilton-connected if and only if it is \(3\)-connected. This generalizes a result by Asratian that a locally connected claw-free graph on at least \(4\) vertices is Hamilton-connected if and only if it is \(3\)-connected [Journal of Graph Theory \(23 (1996) 191-201\)].

We give new expressions for Stirling numbers, and some partial sums of powers and products.

A star coloring of an undirected graph \(G\) is a proper vertex coloring of \(G\) such that any path on four vertices in \(G\) is not bicolored. The star chromatic number \(\chi_s(G)\) of an undirected graph \(G\) is the smallest integer \(k\) for which \(G\) admits a star coloring with \(k\) colors. In this paper, the star chromatic numbers for some infinite subgraphs of Cartesian products of paths and cycles are established. In particular, we show that \(\chi_s(P_i \Box C_j) = 5\) for \(i, j \geq 4\) and \(\chi_s(C_i \Box C_j) = 5\) for \(i, j \geq 30\). We also show that \(\chi_s(P_i \Box P_j \Box P_k) = 6\) for \(i, j, k \geq 4\), \(\chi_s(C_{3} \Box C_{3} \Box C_k) = 7\) for \(k \geq 3\), and \(\chi_s(C_{4i} \Box C_{4j} \Box P_{4k} \Box C_{4l}) \leq 9\) for \(i, j, k, l \geq 1\). Furthermore, we give the star chromatic numbers of \(d\)-dimensional hypercubes for \(d \leq 6\).

Mixed connectivity is a generalization of vertex and edge connectivity. A graph is \((p,0)\)-connected, \(p \geq 0\), if the graph remains connected after removal of any \(p – 1\) vertices. A graph is \((p,q)\)-connected, \(p \geq 0\), \(q \geq 0\), if it remains connected after removal of any \(p\) vertices and any \(q – 1\) edges. Cartesian graph bundles are graphs that generalize both covering graphs and Cartesian graph products. It is shown that if graph \(F\) is \((p_F, q_F)\)-connected and graph \(B\) is \((p_B, q_B)\)-connected, then Cartesian graph bundle \(G\) with fibre \(F\) over the base graph \(B\) is \((p_F + p_B, q_F + q_B)\)-connected. Furthermore, if \(q_F + p_B \geq 0\), then \(G\) is also \((p_F + p_B + 1, q_F + p_B – 1)\)-connected. Finally, let graphs \(G_i\), \(i = 1, \ldots, n\), be \((p_i, q_i)\)-connected and let \(k\) be the number of graphs with \(q_i > 0\). The Cartesian graph product \(G = G_1 \Box G_2 \Box \ldots \Box G_n\) is \((\sum p_i, \sum q_i)\)-connected, and, for \(k \geq 1\), it is also \((\sum p_i + k – 1, \sum q_i – k + 1)\)-connected.

Let \(\gamma_t(D)\) denote the total domination number of a digraph \(D\), and let \(C_m \Box C_n\) denote the Cartesian product graph of \(C_m\) and \(C_n\), where \(C_m\) denotes the directed cycle of length \(m\), \(m \leq n\). In [On domination number of Cartesian product of directed cycles, Information Processing Letters 110 (2010) 171-173], Liu et al. determined the domination number of \(C_2 \Box C_n\), \(C_3 \Box C_n\), and \(C_4 \Box C_n\). In this paper, we determine the exact values of \(\gamma_t(C_m \Box C_n)\) when at least one of \(m\) and \(n\) is even, or \(n\) is odd and \(m = 1, 3, 5,\) or \(7\).

In this paper, a new type of labeled graphs, called modular multiplicative graphs, is introduced and studied. Specifically, we show that every graph is a subgraph of a modular multiplicative graph. Later, we introduce \(k\)-modular multiplicative graphs and prove that certain families of paths and cycles admit such a label. We conclude with several open problems and areas of future possible research, including a note on harmonious graph labels.

Let \(X = (V,E)\) be a digraph. \(X\) is maximally connected if \(\kappa(X) = \delta(X)\). \(X\) is maximally arc-connected if \(\lambda(X) = \delta(X)\). And \(X\) is super arc-connected if every minimum arc-cut of \(X\) is either the set of inarcs of some vertex or the set of outarcs of some vertex. In this paper, we prove that the strongly connected Bi-Cayley digraphs are maximally connected and maximally arc-connected, and most strongly connected Bi-Cayley digraphs are super arc-connected.

A \(2\)-rainbow dominating function (2RDF) of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all subsets of the set \(\{1,2\}\) such that for any vertex \(v \in V(G)\) with \(f(v) = \emptyset\), the condition that there exists \(u \in N(v)\) with \(\bigcup_{u\in N(v)}f(u) = \{1,2\}\) is fulfilled, where \(N(v)\) is the open neighborhood of \(v\). A rainbow dominating function \(f\) is said to be a rainbow restrained domination function if the induced subgraph of \(G\) by the vertices with label \(\emptyset\) has no isolated vertex. The weight of a rainbow restrained dominating function is the value \(w(f) = \sum_{u \in V(G)} |f(u)|\). The minimum weight of a rainbow restrained dominating function of \(G\) is called the rainbow restrained domination number of \(G\). In this paper, we initiate the study of the rainbow restrained domination number and we present some bounds for this parameter.

For a finite group \(G\), let \(P(m,n,G)\) denote the probability that a \(m\)-subset and an \(n\)-subset of \(G\) commute elementwise, and let \(P(n,G) = P(1,n,G)\) be the probability that an element commutes with an \(n\)-subset of \(G\). Some lower and upper bounds are given for \(P(m,n,G)\), and it is shown that \(\{P(m,n,G)\}_{m,n}\) is decreasing with respect to \(m\) and \(n\). Also, \(P(m,n,G)\) is computed for some classes of finite groups, including groups with a central factor of order \(p^2\) and \(P(n,G)\) is computed for groups with a central factor of order \(p^3\) and wreath products of finite abelian groups.