Search

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being uncolored. At each discrete time interval, a colored vertex with exactly one uncolored neighbor forces this uncolored neighbor to be colored. The initial set S is a zero forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The zero forcing number Z(G) of G is the minimum cardinality of a zero forcing set of G. In this paper, we prove that if G is a connected, cubic, claw-free graph of order $$n \ge 6$$, then $$Z(G) \le \alpha (G) + 1$$ where $$\alpha (G)$$ denotes the independence number of G. Further we prove that if $$n \ge 10$$, then $$Z(G) \le \frac{1}{3}n + 1$$. Both bounds are shown to be best possible.

In a recent paper, Das introduced the graph $$\mathcal {I}n(\mathbb {V})$$ , called subspace inclusion graph on a finite dimensional vector space $$\mathbb {V}$$ , where the vertex set is the collection of nontrivial proper subspaces of $$\mathbb {V}$$ and two vertices are adjacent if one is properly contained in another. Das studied the diameter, girth, clique number and chromatic number of $$\mathcal {I}n(\mathbb {V})$$ when the base field is arbitrary, and he also studied some other properties of $$\mathcal {I}n(\mathbb {V})$$ when the base field is finite. At the end of the above paper, the author posed the open problem of determining the automorphisms of $$\mathcal {I}n(\mathbb {V})$$ . In this paper, we give the answer to the open problem.

Let G be an edge-colored graph. A rainbow (heterochromatic, or multicolored) path of G is such a path in which no two edges have the same color. Let the color degree of a vertex v to be the number of different colors that are used on edges incident to v, and denote it by $$d^c(v)$$ . In a previous paper, we showed that if $$d^c(v)\ge k$$ (color degree condition) for every vertex v of G, then G has a rainbow path of length at least $$\lceil (k+1)/2\rceil $$ . Later, in another paper we first showed that if $$k\le 7$$ , G has a rainbow path of length at least $$k-1$$ , and then, based on this we used induction on k and showed that if $$k\ge 8$$ , then G has a rainbow path of length at least $$\lceil (3k)/5\rceil +1$$ . In 2010, Gyarfas and Mhalla showed that in any proper edge-colored complete graph $$K_n$$ , there is a rainbow path with no less than $$(2n+1)/3$$ vertices. In the present paper, by using a simpler approach we further improve the result by showing that if $$k\ge 8$$ , G has a rainbow path of length at least $$\lceil (2k)/3\rceil +1$$ .

A connected graph \(G\) is optimal-\(\kappa \) if the connectivity \(\kappa (G)=\delta (G)\), where \(\delta (G)\) is the minimum degree of \(G\). It is super-\(\kappa \) if every minimum vertex cut isolates a vertex. An optimal-\(\kappa \) graph \(G\) is \(m\)-optimal-\(\kappa \) if for any vertex set \(S\subseteq V(G)\) with \(|S|\le m\), \(G-S\) is still optimal-\(\kappa \). The maximum integer of such \(m\), denoted by \(O_{\kappa }(G)\), is the vertex fault tolerance of \(G\) with respect to the property of optimal-\(\kappa \). The concept of vertex fault tolerance with respect to the property of super-\(\kappa \), denoted by \(S_{\kappa }(G)\), is defined in a similar way. In a previous paper, we have proved that \(\min \{\kappa _1(G)-\delta (G),\delta (G)-1\}\le O_\kappa (G)\le \delta (G)-1\) and \(\min \{\kappa _1(G)-\delta (G)-1,\delta (G)-1\}\le S_\kappa (G)\le \delta (G)-1\). We also have \(S_\kappa (G)\le O_\kappa (G)\le \delta (G)-1\). In this paper, we study the realizability problems concerning the above three bounds. By construction, we proved that for any non-negative integers \(a,b,c\) with \(a\le b\le c\), (i) there exists a graph \(G\) such that \(\kappa _1(G)-\delta (G)=a\), \(O_{\kappa }(G)=b\), and \(\delta (G)-1=c\); (ii) there exists a graph \(G\) with \(\kappa _1(G)-\delta (G)-1=a\), \(S_{\kappa }(G)=b\), and \(\delta (G)-1=c\); and (iii) there exists a graph \(G\) such that \(S_{\kappa }(G)=a\), \(O_{\kappa }(G)=b\), and \(\delta (G)-1=c\).

The Wiener index is one of the most widely studied parameters in chemical graph theory. It is defined as the sum of the lengths of the shortest paths between all unordered pairs of vertices in a given graph. In 1991, Soltes posed the following problem regarding the Wiener index: Find all graphs such that its Wiener index is preserved upon removal of any vertex. The problem is far from being solved, and to this day, only one graph with such property is known: the cycle graph on 11 vertices. In this paper, we solve a relaxed version of the problem, proposed by Knor et al. in 2018. For a given k, the problem is to find (infinitely many) graphs having exactly k vertices such that the Wiener index remains the same after removing any of them. We call these vertices good vertices, and we show that there are infinitely many cactus graphs with exactly k cycles of length at least 7 that contain exactly 2k good vertices and infinitely many cactus graphs with exactly k cycles of length $$c \in \{5,6\}$$ that contain exactly k good vertices. On the other hand, we prove that G has no good vertex if the length of the longest cycle in G is at most 4.

The connective eccentricity index is a degree-distance-based graph invariant, while the modified second Zagreb index is a degree-based graph invariant. The Parikh word representable graph is a new class of graphs G(w), which corresponds to words w that are finite sequence of symbols. In this paper, we first present explicit formulas for the connective eccentricity index and modified second Zagreb index of the Parikh word representable graphs corresponding to binary core words of the form aub over a binary alphabet $$\{a,\,b\}$$ , respectively. Then, we investigate the relationship between the connective eccentricity index and modified second Zagreb index and obtain some comparative results about these two indices.

Given a finite graph G, the maximum length of a sequence $$(v_1,\ldots ,v_k)$$ of vertices in G such that each $$v_i$$ dominates a vertex that is not dominated by any vertex in $$\{v_1,\ldots ,v_{i-1}\}$$ is called the Grundy domination number, $$\gamma _\mathrm{gr}(G)$$ , of G. A small modification of the definition yields the Z-Grundy domination number, which is the dual invariant of the well-known zero forcing number. In this paper, we prove that $$\gamma _\mathrm{gr}(G) \ge \frac{n + \lceil \frac{k}{2} \rceil - 2}{k-1}$$ holds for every connected k-regular graph of order n different from $$K_{k+1}$$ and $$\overline{2C_4}$$ . The bound in the case $$k=3$$ reduces to $$\gamma _\mathrm{gr}(G)\ge \frac{n}{2}$$ , and we characterize the connected cubic graphs with $$\gamma _\mathrm{gr}(G)=\frac{n}{2}$$ . If G is different from $$K_4$$ and $$K_{3,3}$$ , then $$\frac{n}{2}$$ is also an upper bound for the zero forcing number of a connected cubic graph, and we characterize the connected cubic graphs attaining this bound.

The independence polynomial of a graph G is $$I(G;x)=\sum _{k=0}^{\alpha (G)} s_{k}\cdot x^{k}$$ , where $$s_{k}$$ and $$\alpha (G)$$ denote the number of independent sets of cardinality k and the independence number of G, respectively. We say that a cycle is a $$\tilde{3}$$ -cycle if its length is divisible by 3, otherwise a non- $$\tilde{3}$$ -cycle. Define $$\phi (G)$$ to be the decycling number of G. Engstrom proved that $$|I(G;-1)| \le 2^{\phi (G)}$$ for any graph G. In this paper, we first prove that $$|I(G;-1)|\le 2^{\beta (G)}-\beta (G)$$ for graphs with non- $$\tilde{3}$$ -cycles, where $$\beta (G)$$ is the cyclomatic number of G. Infinitely many examples show that there do exist graphs satisfying $$\beta (G)=\phi (G)$$ and containing non- $$\tilde{3}$$ -cycles. In such a case, it improves the Engstrom’s result. Furthermore, $$|I(G;-1)|\le 2^{k}$$ provided that all cycles of G are pairwise disjoint, where k is the number of $$\tilde{3}$$ -cycles of G. This provides a new perspective on estimating the independence polynomial at -1 of many special graphs. In the case G contains no vertices of degree 1, $$|I(G;-1)|\le 2^{\beta (G)}-1$$ if $$\beta (G)\ge 2$$ , and $$|I(G;-1)|\le 2^{\beta (G)-1}$$ if G contains a non- $$\tilde{3}$$ -cycle.

For an edge-colored graph $G$, a set $F$ of edges of $G$ is called a \emph{proper cut} if $F$ is an edge-cut of $G$ and any pair of adjacent edges in $F$ are assigned by different colors. An edge-colored graph is \emph{proper disconnected} if for each pair of distinct vertices of $G$ there exists a proper edge-cut separating them. For a connected graph $G$, the \emph{proper disconnection number} of $G$, denoted by $pd(G)$, is the minimum number of colors that are needed in order to make $G$ proper disconnected. In this paper, we first give the exact values of the proper disconnection numbers for some special families of graphs. Next, we obtain a sharp upper bound of $pd(G)$ for a connected graph $G$ of order $n$, i.e, $pd(G)\leq \min\{ \chi'(G)-1, \left \lceil \frac{n}{2} \right \rceil\}$. Finally, we show that for given integers $k$ and $n$, the minimum size of a connected graph $G$ of order $n$ with $pd(G)=k$ is $n-1$ for $k=1$ and $n+2k-4$ for $2\leq k\leq \lceil\frac{n}{2}\rceil$., Comment: 14 pages

A set of vertices W of a graph G is a resolving set if every vertex of G is uniquely determined by its vector of distances to W. In this paper, the Maker–Breaker resolving game is introduced. The game is played on a graph G by Resolver and Spoiler who alternately select a vertex of G not yet chosen. Resolver wins if at some point the vertices chosen by him form a resolving set of G, whereas Spoiler wins if the Resolver cannot form a resolving set of G. The outcome of the game is denoted by o(G), and $$R_{\mathrm{MB}}(G)$$ (resp. $$S_{\mathrm{MB}}(G)$$ ) denotes the minimum number of moves of Resolver (resp. Spoiler) to win when Resolver has the first move. The corresponding invariants for the game when Spoiler has the first move are denoted by $$R'_{\mathrm{MB}}(G)$$ and $$S'_\mathrm{MB}(G)$$ . Invariants $$R_{\mathrm{MB}}(G)$$ , $$R'_{\mathrm{MB}}(G)$$ , $$S_\mathrm{MB}(G)$$ , and $$S'_{\mathrm{MB}}(G)$$ are compared among themselves and with the metric dimension $$\mathrm{dim}(G)$$ . A large class of graphs G is constructed for which $$R_{\mathrm{MB}}(G) > \mathrm{dim}(G)$$ holds. The effect of twin equivalence classes and pairing resolving sets on the Maker–Breaker resolving game is described. As an application, o(G), as well as $$R_{\mathrm{MB}}(G)$$ and $$R'_{\mathrm{MB}}(G)$$ (or $$S_{\mathrm{MB}}(G)$$ and $$S'_{\mathrm{MB}}(G)$$ ), is determined for several graph classes, including trees, complete multi-partite graphs, grid graphs, and torus grid graphs.

The Balaban index and sum-Balaban index of a connected (molecular) graph G are defined as $$\begin{aligned} J(G)&=\frac{m}{\mu +1} \sum _{uv\in E(G)}\frac{1}{\sqrt{\sigma _{G}(u)\sigma _{G}(v)}}~ \text{ and }\\ SJ(G)&=\frac{m}{\mu +1} \sum _{uv\in E(G)}\frac{1}{\sqrt{\sigma _{G}(u)+\sigma _{G}(v)}}, \end{aligned}$$ respectively, where m is the number of edges, $$\mu $$ is the cyclomatic number, $$\sigma _G(u)$$ is the sum of distances between vertex u and all other vertices of G. In this paper, we establish that $$\begin{aligned} K\left( DS(n-3,\,1)\right)>K\left( DS(n-4,\,2)\right)>\cdots >K \left( DS\left( \left\lceil \frac{n}{2}\right\rceil -1,\, \left\lfloor \frac{n}{2}\right\rfloor -1\right) \right) \end{aligned}$$ $$(K=J,\,SJ),$$ where $$DS(p,\,q)$$ is a double star on $$n\,(=p+q+2,\,p\ge q)$$ vertices. As an application, we determine the extremal graphs of the Balaban index and the sum-Balaban index in the class of chain graphs G on n vertices, where G is a tree or a unicyclic graph. Finally, we give an open problem on Balaban (sum-Balaban) index of connected chain graphs.

Let $k$ be an positive integer. For any two integers $i$ and $j$ in $\{0,1,\dots,k-1\}$, let $|i-j|_k=\min\{|i-j|,k-|i-j|\}$ be the circular distance between $i$ and $j$. Let $t$ be a nonnegative integer. Suppose $f$ is a mapping from $V(G)$ to $\{0,1,\dots,k-1\}$. If adjacent vertices receive different integers, and for each vertex $u$ of $G$, the number of neighbors $v$ of $u$ with $|f(u)-f(v)|_k=1$ is at most $t$, then $f$ is called a $t$-relaxed 2-distant circular $k$-coloring, or simply a $(\frac{k}{2},t)^*$-coloring of $G$. If $G$ has a $(\frac{k}{2},t)^*$-coloring, then $G$ is called $(\frac{k}{2},t)^*$-colorable. In this paper, we prove that, for any two fixed integers $k$ and $t$ with $k\geq2$ and $t\geq1$, deciding whether $G$ is $(\frac{k}{2},t)^*$-colorable is NP-complete expect the case $k=2$ and the case $k=3$ and $t\leq3$, which are polynomially solvable. For any outerplanar graph $G$, e show that all outerplanar graphs are $(\frac{5}{2},4)^*$-colorable, we prove that there is no fixed positive integer $t$ such that all outerplanar graphs are $(\frac{4}{2},t)^*$-colorable., Comment: 19 pages, 8 figures

A proper [k]-total coloring c of a graph G is a proper total coloring c of G using colors of the set $$[k]=\{1,2,\ldots ,k\}$$ . Let $$\Sigma (u)$$ denote the sum of the color on a vertex u and the colors on all the edges incident with u. For each edge $$uv\in E(G)$$ , if $$\Sigma (u)\ne \Sigma (v)$$ , then we say the coloring distinguishes adjacent vertices by sum and call it a neighbor sum distinguishing total coloring of G. By $$tndi_{\Sigma }(G)$$ , we denote the minimal value of k in such a coloring of G. It has been conjectured by Pilśniak et al. that $$\Delta (G)+3$$ colors enable the existence of a neighbor sum distinguishing total coloring. In this paper, we consider the neighbor sum distinguishing total coloring of corona product $$G\circ H$$ and obtain that $$tndi_{\Sigma }(G\circ H)\le \Delta (G\circ H)+3$$ .

Let $$k\ge 4$$ be an integer, and let G be a graph with maximum degree $$\Delta $$ . In 1991, Alon, McDiarmid and Reed proved that G has a proper coloring using $$O(\Delta ^{(k-1)/(k-2)})$$ colors such that G does not have bichromatic paths with k vertices. In this paper, we improve this result by showing G has a proper coloring using $$(1+\lceil k/2\rceil ^{1/(k-3)})\Delta ^{(k-1)/(k-2)}+\Delta +1$$ colors such that G does not have bichromatic paths with k vertices. We remark that there exists a graph G with maximum degree $$\Delta $$ such that for any proper coloring of G using $$\Omega (\frac{\Delta ^{(k-1)/(k-2)}}{(\log \Delta )^{1/(k-2)}})$$ colors, there is always a bichromatic path with k vertices. Using the similar method, we also show that G has a proper coloring using $$O(\Delta ^{4/3})$$ colors such that G contains neither bichromatic cycles nor bichromatic paths with order 5.

For a simple connected graph G, the Q-generating function of the numbers $$N_k$$ of semi-edge walks of length k in G is defined by $$W_Q(t)=\sum \nolimits _{k = 0}^\infty {N_k t^k }$$ . This paper reveals that the Q-generating function $$W_Q(t)$$ may be expressed in terms of the Q-polynomials of the graph G and its complement $$\overline{G}$$ . Using this result, we study some Q-spectral properties of graphs and compute the Q-polynomials for some graphs obtained from various graph operations, such as the complement graph of a regular graph, the join of two graphs and the (edge)corona of two graphs. As another application of the Q-generating function $$W_Q(t)$$ , we also give a combinatorial interpretation of the Q-coronal of G, which is defined to be the sum of the entries of the matrix $$(\lambda I_n-Q(G))^{-1}$$ . This result may be used to obtain the many alternative calculations of the Q-polynomials of the (edge)corona of two graphs. Further, we also compute the Q-generating functions of the join of two graphs and the complete multipartite graphs.

Let $$n >3$$ and $$ 0< k < \frac{n}{2} $$ be integers. In this paper, we investigate some algebraic properties of the line graph of the graph $$ {Q_n}(k,k+1) $$ where $$ {Q_n}(k,k+1) $$ is the subgraph of the hypercube $$Q_n$$ which is induced by the set of vertices of weights k and $$k+1$$ . The graph $$ {Q_n}(k,k+1) $$ has a close relation to Johnson graph $$J(n+1,k+1)$$ . In fact, it is the square root of the graph $$J(n+1,k+1)$$ . We will see that when $$ n\ne 2k+1$$ , then the graph $$ {Q_n}(k,k+1) $$ is a non-regular edge-transitive graph; hence, its line graph is a vertex-transitive graph. In the first step, we determine the automorphism groups of these graphs for all values of n, k. In the second step, we study Cayley properties of the line graphs of these graphs. In particular, we show that if $$k\ge 3$$ and $$ n \ne 2k+1$$ , then except for the cases $$(k,n) \ne (3,9)$$ and $$(k,n) \ne (3,33)$$ , the line graph of the graph $$ {Q_n}(k,k+1) $$ is a vertex-transitive non-Cayley graph. Also, we show that the line graph of the graph $$ {Q_n}(1,2) $$ is a Cayley graph if and only if n is a power of a prime p. Moreover, we show that for ‘almost all’ even values of k, the line graph of the graph $$ {Q_{2k+1}}(k,k+1) $$ is a vertex-transitive non-Cayley graph.

Let G be a nontrivial connected graph with a vertex-coloring c: $$V(G)\rightarrow \{1,2,\ldots ,q\},q\in N$$ . For a set $$S\subseteq V(G)$$ and $$|S|\ge 2$$ , a subtree T of G satisfying $$S\subseteq V(T)$$ is said to be an S-Steiner tree or simply S-tree. The S-tree T is called a vertex-rainbow S-tree if the vertices of $$V(T)\setminus S$$ have distinct colors. Let k be a fixed integer with $$2\le k\le |V(G)|$$ , if every k-subset S of V(G) has a vertex-rainbow S-tree, then G is said to be vertex-rainbow k-tree connected. The k-vertex-rainbow index of G, denoted by $$rvx_{k}(G)$$ , is the minimum number of colors that are needed in order to make G vertex-rainbow k-tree connected. In this paper, we study the 3-vertex-rainbow index of unicyclic graphs and complementary graphs, respectively.

A Roman dominating function on a graph G is a function $$f:V(G)\rightarrow \{0,1,2\}$$ satisfying the condition that every vertex u for which $$f(u) = 0$$ is adjacent to at least one vertex v for which $$f(v) =2$$ . A Roman dominating function f is called a restrained Roman dominating function if the induced subgraph of G by the vertices with label 0 has no isolated vertex. The weight of a restrained Roman dominating function is the value $$\omega (f)=\sum _{u\in V(G)} f(u)$$ . The minimum weight of a restrained Roman dominating function of G is called the restrained Roman domination number of G and denoted by $$\gamma _{rR}(G)$$ . In this paper, we show that for any graph G of order $$n\ge 5$$ , $$6\le \gamma _{rR} (G)+\gamma _{rR} ({\overline{G}})\le n+5$$ and characterize all the extremal graphs. In addition, we classify all graphs with large restrained Roman domination number.

Let $$K_n-C_{k}$$ denote the graph obtained from the complete graph $$K_n$$ by deleting k edges of a cycle $$C_k$$ , that is, a nearly complete graph. In this paper, we completely determine the structure of the sandpile group of $$K_{n}-C_{k}$$ for $$3\le k\le n-2$$ .

A subset D of the vertex set of a graph $$\Gamma $$ is a dominating set for $$\Gamma $$ if each vertex of $$\Gamma $$ is either in D or has a neighbor in D. The size of a minimum cardinality dominating set of a graph is its domination number. In this paper, we initiate the study of domination in a well-known family of rather symmetric tetravalent graphs known as the Rose window graphs. We compare their domination number to the domination number of their spanning generalized Petersen subgraphs, which have been studied quite extensively in the literature.

A subset D of the vertex set V(G) of a graph G is called a [1, k]-dominating set if every vertex from $$V-D$$ is adjacent to at least one vertex and at most k vertices of D. A [1, k]-dominating set with minimum number of vertices is called a $$\gamma _{[1,k]}(G)$$ -set, and the number of its vertices is called the [1, k]-domination number of G and is denoted by $$\gamma _{[1,k]}(G)$$ . In this paper, we express the computation of the [1, k]-domination number of lexicographic products $$G\circ H$$ as an optimization problem over certain partitions of V(G). Nonetheless, in special cases explicit formulas are possible.

The irregularity of a graph G is the sum of $$|\mathrm{deg}(u) - \mathrm{deg}(v)|$$ over all edges uv of G. In this paper, this invariant is considered on $$\pi $$ -permutation graphs, Fibonacci cubes, and trees. An upper bound on the irregularity of $$\pi $$ -permutations graphs is given, and $$\pi $$ -permutation graphs that attain the equality are characterized. The concept of the irregularity is extended to arbitrary edge subsets and applied to permutation edges of $$\pi $$ -permutation graphs. An exact formula for the irregularity of Fibonacci cubes is proved. An upper bound on the irregularity of trees in terms of the diameter is given, and trees that attain the equality are characterized.

An Italian dominating function on a graph G with vertex set V(G) is a function $$f :V(G) \rightarrow \{0,1,2\}$$ having the property that for every vertex v with $$f(v) = 0$$ , at least two neighbors of v are assigned 1 under f or at least one neighbor of v is assigned 2 under f. The weight of an Italian dominating function f is the sum of the values assigned to all the vertices under f. The Italian domination number of G, denoted by $$\gamma _{I}(G)$$ , is the minimum weight of an Italian dominating of G. It is known that if G is a connected graph of order $$n \ge 3$$ , then $$\gamma _{I}(G) \le \frac{3}{4}n$$ . Further, if G has minimum degree at least 2, then $$\gamma _{I}(G) \le \frac{2}{3}n$$ . In this paper, we characterize the connected graphs achieving equality in these bounds. In addition, we prove Nordhaus–Gaddum inequalities for the Italian domination number.

Computing the crossing number of a graph is NP-hard. In the paper, for a disconnected 6-vertex graph $$Q =C_{5}\cup K_{1}$$ , we obtain the crossing number $$Z(6,n)+\lfloor \frac{n}{2}\rfloor $$ of the graph $$Q_{n}$$ which is the join product of Q with the discrete graph by introducing the “rotation” method. Moreover, we give crossing numbers for join products of Q with the path and the cycle. Besides, we also get directly crossing numbers for join products of some connected 6-vertex graphs with the path and the cycle, some of which were studied by M. Klesc, D. Kravecova, and J. Petrillova.

The proper connection number of a graph G, denoted by pc(G), is the minimum number of colors needed to color the edges of G so that every pair of distinct vertices of G is connected by a path in which no two adjacent edges of the path receive the same color. A connected graph G is k-PC if pc(G) ≤ k. In the literature, it is shown that every 3-edge-connected graph is 2-PC and every 2-edge-connected graph is 3-PC. We show in this paper that every 2-connected graph such that each edge is contained in a cycle of length at most 4 is 2-PC, and every 2-connected graph with minimum degree at least 3 such that each edge is contained in a cycle of length at most 6 is 2-PC.

The 2-distance vertex-distinguishing index $$\chi '_\mathrm{d2}(G)$$ of a graph G is the minimum number of colors required for a proper edge coloring of G such that any pair of vertices at distance two have distinct sets of colors. It was conjectured that every subcubic graph G has $$\chi '_{\mathrm{d2}}(G)\le 5$$. In this paper, we confirm this conjecture for subcubic graphs with maximum average degree less than $$\frac{8}{3}$$.

The adjacent vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that the edge coloring set on any pair of adjacent vertices is distinct. The minimum number of colors required for an adjacent vertex distinguishing edge coloring of G is denoted by $$\chi _{a}'(G)$$. It is observed that $$\chi _a'(G)\ge \Delta (G)+1$$ when G contains two adjacent vertices of degree $$\Delta (G)$$. In this paper, we prove that if G is a planar graph without 4-cycles, then $$\chi _a'(G)\le \max \{9,\Delta (G)+1\}$$.

In this paper, we determine the unique maximum (or minimum) extremal graph for general spectral radius, zeroth-order general Randic index, general sum-connectivity index, general Platt index, second Zagreb index and multiplicative Zagreb indices in the class of cacti with $$n\ge 4$$ vertices and $$k\ge 0$$ cycles. By applying our new result, we demonstrate the unique maximum extremal graph for general spectral radius, zeroth-order general Randic index, general sum-connectivity index, general Platt index, second Zagreb index and second multiplicative Zagreb index in the class of cacti with $$n\ge 4$$ vertices. Furthermore, we also determine the unified maximum extremal graphs for general spectral radius, zeroth-order general Randic index and the second multiplicative Zagreb index in the class of cacti with $$n\ge 4$$ vertices and $$k\ge 1$$ pendant vertices.

The strong geodetic number, $$\text {sg}(G),$$ of a graph G is the smallest number of vertices such that by fixing a suitable geodesic between each pair of selected vertices, all vertices of the graph are covered. In this paper, the formula for $$\text {sg}(K_{n,m})$$ is given, as well as a formula for the crown graphs $$S_n^0$$. Bounds on the strong geodetic number of the hypercube $$Q_n$$ are also discussed.

A graph G is called $$K_{1,5}$$-free if G contains no $$K_{1,5}$$ as an induced subgraph. A tree with at most m leaves is called an m-ended tree. Let $$\sigma _k(G)$$ denote the minimum degree sum of k independent vertices in G. In this paper, it is shown that every connected $$K_{1,5}$$-free graph G contains a spanning 5-ended tree if $$\sigma _6(G)\ge |G|-1$$.

A graph is split if there is a partition of its vertex set into a clique and an independent set. In this paper, we determine when the Gruenberg–Kegel graph, the solvable graph, and the compact forms of these graphs associated with finite nonabelian simple groups are split. In particular, it is proved that the compact form of the Gruenberg–Kegel graph of any finite simple group is split.

Let T be a tree, a vertex of degree one is called a leaf. The set of leaves of T is denoted by $${\mathrm{Leaf}}(T)$$. The subtree $$T-{\mathrm{Leaf}}(T)$$ of T is called the stem of T and denoted by $${\mathrm{Stem}}(T)$$. In this paper, we give a sharp sufficient condition to show that a $$K_{1,t}$$-free graph has a spanning tree whose stem has a few leaves. By applying the main result, we give improvements of previous related results.

The k-component connectivity $$c\kappa _{k}(G)$$ of a non-complete graph G is the minimum number of nodes whose deletion results in a graph with at least k components. A node subset S of G is called an optimal k-component cut if $$|S|=c\kappa _{k}(G)$$ and $$G-S$$ has exactly k components. In this paper, we determine the component connectivity of the locally twisted cube $$LTQ_{n}$$, i.e. $$c\kappa _{k+1}(LTQ_{n})=kn-k(k+1)/2+1$$ for $$1\le k\le n-1$$, $$n\ge 2$$, and characterize optimal k-component cuts of $$LTQ_{n}$$.

Two vertices in a graph are said to 2-step dominate each other if they are at distance 2 apart. A set S of vertices in a graph G is a hop dominating set of G if every vertex outside S is 2-step dominated by some vertex of S. The hop domination number, $$\gamma _{h}(G)$$, of G is the minimum cardinality of a hop dominating set of G. A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to at least one vertex of S. The total domination number, $$\gamma _{t}(G)$$, of G is the minimum cardinality of a total dominating set of G. It is known that if G is a triangle-free graph, then $$\gamma _{h}(G)\le \gamma _{t}(G)$$. But there are connected graphs G for which the difference $$\gamma _{h}(G)-\gamma _{t}(G)$$ can be made arbitrarily large. It would be interesting to find other classes of graphs G that satisfy $$\gamma _{h}(G)\le \gamma _{t}(G)$$. In this paper, we study the relationship between total domination number and hop domination number in diamond-free graph. We prove that if G is diamond-free graph of order n with the exception of two special graphs, then $$\gamma _{h}(G)- \gamma _{t}(G)\le \frac{n}{6}$$. Furthermore, we find two subclasses of diamond-free graphs G that satisfy $$\gamma _{h}(G)\le \gamma _{t}(G)$$ and generalize the known result.

The augmented Zagreb index (AZI index) of a graph $$G=(V,E)$$ , which is a valuable predictive index in the study of the heat of formation in octanes and heptanes, is defined as $$\begin{aligned} \hbox {AZI}(G)=\sum _{uv\in E(G)}\left( \frac{d_{u}d_{v}}{d_{u}+d_{v}-2}\right) ^{3}{,} \end{aligned}$$ where $$d_{u}$$ and $$d_{v}$$ are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we give the expressions for computing the augmented Zagreb indices of fluoranthene-type benzenoid systems, and we determine the extremal values of augmented Zagreb index in f-benzenoid systems with h hexagons. Especially, we give the extremal values of augmented Zagreb index in cata-catacondensed fluoranthene-type benzenoid systems with h hexagons.

The total-coloring of a graph is a coloring of the edge set and vertex set. A path in a total-colored graph is a total proper path if the coloring of the edges and internal vertices is proper, that is, any two adjacent or incident elements of edges and internal vertices on the path differ in color. For a connected graph G, the total proper connection number of G, denoted by tpc(G), is defined as the smallest number of colors such that any two vertices of the graph are connected by a total proper path of G. These concepts are inspired by the concepts of total chromatic number $$\chi ''(G)$$ , proper connection number pc(G) and proper vertex connection number pvc(G) of a connected graph G. In this paper, we first determine the value of the total proper connection number tpc(G) for some special graphs G. Secondly, we obtain that $$tpc(G)\le 4$$ for any 2-(edge-)connected graph G and give examples to show that the upper bound 4 is sharp. For general graphs, we also obtain sharp upper bounds for tpc(G) in terms of the maximum degree of a vertex incident with a bridge in G and the minimum degree, respectively. Finally, we compare tpc(G) with pvc(G) and pc(G), respectively, and obtain that $$tpc(G)>pvc(G)$$ for any nontrivial connected graph G and that there exist graphs G such that $$tpc(G)=pc(G)+t$$ for $$0\le t\le 2$$ .

The general sum-connectivity index of a graph G is defined as $$\chi _\alpha (G)=\sum _{uv\in E(G)}(d(u)+d(v))^{\alpha }$$, where d(u) denotes the degree of a vertex u in G and $$\alpha $$ is a real number. In this paper, we determine the minimum general sum-connectivity indices of trees with n vertices and matching number m, where $$n=2m$$ for $$\alpha \le -\,2$$ and $$2m\le n\le 3m+1$$ for $$\alpha >1$$, respectively. The corresponding extremal graphs are also characterized.

Let $$G=(V,E)$$ be a graph with no isolated vertex. A subset $$S\subseteq V(G)$$ is a total dominating set of graph G if every vertex in V(G) is adjacent to at least one vertex in S. A total dominating set S of graph G is a locating-total dominating set if for every pair of distinct vertices $$u_1$$ and $$u_2$$ in $$V(G)-S$$, $$N(u_1)\cap S\ne N(u_2)\cap S$$. The locating-total domination number of graph G, denoted by $$\gamma _t^L(G)$$, is the minimum cardinality of a locating-total dominating set of G. In this paper, we investigate the bounds of locating-total domination number of grid graphs.

A strong edge-coloring of a graph G is a proper edge-coloring such that every path of length 3 uses three different colors. The strong chromatic index of a graph G, denoted by $$\chi _{s}^\prime (G)$$, is the minimum number of colors needed for a strong edge-coloring of G. In this paper, we show that $$\chi _{s}^\prime (G)\le 3\Delta -2$$ for any pseudo-Halin graph G with $$\Delta \ge 4$$.

The revised Szeged index of a connected graph G is defined as $$\begin{aligned} Sz^*(G)=\sum _{e=uv\in E(G)}\left( n_u(e|G)+{\frac{n_0(e|G)}{2}}\right) \left( n_v(e|G)+{\frac{n_0(e|G)}{2}}\right) , \end{aligned}$$where E(G) is the edge set of G, and for any $$e = uv\in E(G)$$, $$n_u(e|G)$$ is the number of vertices of G lying closer to vertex u than to v, $$n_v(e|G)$$ is the number of vertices of G lying closer to vertex v than to u, and $$n_0(e|G)$$ is the number of vertices with equal distances from both end vertices of the edge e. In this paper, we characterize the graph with the minimum revised Szeged index among all the unicyclic graphs with given order and diameter.

A single-cone tree (unicyclic graph) is the join of a complete graph $$K_1$$ and a tree (unicyclic graph). Suppose $$\pi =(d_1, d_2, \ldots , d_n)$$ and $$\pi ^{\,\prime }=(d_1^{\,\prime }, d_2^{\,\prime }, \ldots , d_n^{\,\prime })$$ are two non-increasing degree sequences. We say $$\pi $$ is majorizated by $$\pi ^{\,\prime }$$, denoted by $$\pi \lhd \pi ^{\,\prime }$$, if and only if $$\pi \ne \pi ^{\,\prime }$$, $$\sum \nolimits _{i=1}^{n} d_i=\sum \nolimits _{i=1}^{n} d_i^{\,^{\,\prime }}$$, and $$\sum \nolimits _{i=1}^j d_i\le \sum \nolimits _{i=1}^j d_i^{\,^{\,\prime }}$$ for all $$j=1, 2, \ldots , n-1$$. We use $$J_{\pi }$$ to denote the class of single-cone trees (unicyclic graphs) with degree sequence $$\pi $$. Suppose that $$\pi $$ and $$\pi ^{\,\prime }$$ are two different non-increasing degree sequences of single-cone trees (unicyclic graphs). Let $$\rho $$ and $$\rho ^{\,\prime }$$ be the largest spectral radius of the graphs in $$J_{\pi }$$ and $$J_{\pi ^{\,\prime }}$$, respectively, $$\mu $$ and $$\mu ^{\,\prime }$$ be the largest signless Laplacian spectral radius of the graphs in $$J_{\pi }$$ and $$J_{\pi ^{\,\prime }}$$, respectively. In this paper, we prove that if $$\pi \lhd \pi ^{\,\prime }$$, then $$\rho

Let G be a graph and $$v\in V(G)$$. The neighbors of v, denoted by N(v), are the set of vertices adjacent to v. Let $$N[v]=N(v)\cup \{v\}$$ and $$J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$$. A graph G is called quasi-claw-free if $$J(u,v)\ne \emptyset $$ for any $$u,v\in V(G)$$ with $$d(u,v)=2$$. In this paper, we show that if G is a connected quasi-claw-free graph with $$\sigma _{k+1}(G)\ge |G|-k,$$ then G contains a spanning k-ended tree, which generalizes some known results.

Let G be a graph and A(G) the adjacency matrix of G. The polynomial $$\pi (G,x)=\mathrm {per}(xI-A(G))$$ is called the permanental polynomial of G, and the permanental sum of G is the summation of the absolute values of the coefficients of $$\pi (G,x)$$ . In this paper, we give some upper and lower bounds for the permanental sum among spiro hexagonal chains, and the corresponding extremal graphs are determined. Furthermore, we investigate the more general result about permanental sum. We obtain a lower bound for the permanental sum of bipartite graphs and the corresponding extremal graphs are also determined.

Let $$\gamma _\mathrm{tg}(G)$$ denote the game total domination number of a graph G, and let G|v mean that a vertex v of G is declared to be already totally dominated. A graph G is total domination game critical if $$\gamma _\mathrm{tg}(G|v) < \gamma _\mathrm{tg}(G)$$ holds for every vertex v in G. If $$\gamma _\mathrm{tg}(G) = k$$ , then G is further called k- $$\gamma _\mathrm{tg}$$ -critical. In this paper, we prove that the circular ladder $$C_{4k} \,\square \,K_2$$ is 4k- $$\gamma _{\mathrm{tg}}$$ -critical and that the Mobius ladder $$\mathrm{ML}_{2k}$$ is 2k- $$\gamma _{\mathrm{tg}}$$ -critical.

The metric dimension is quite a well-studied graph parameter. Recently, the local metric dimension and the adjacency dimension have been introduced and studied. In this paper, we give a general formula for the local metric dimension of the lexicographic product $$G \circ \mathcal {H}$$ of a connected graph G of order n and a family $$\mathcal {H}$$ composed of n graphs. We show that the local metric dimension of $$G \circ \mathcal {H}$$ can be expressed in terms of the numbers of vertices in the true twin equivalence classes of G, and the local adjacency dimension of the graphs in $$\mathcal {H}$$ .

A recent variation of the classical geodetic problem, the strong geodetic problem, is defined as follows. If G is a graph, then $$\mathrm{sg}(G)$$ is the cardinality of a smallest vertex subset S, such that one can assign a fixed geodesic to each pair $$\{x,y\}\subseteq S$$ so that these $$\left( {\begin{array}{c}|S|\\ 2\end{array}}\right) $$ geodesics cover all the vertices of G. In this paper, the strong geodetic problem is studied on Cartesian product graphs. A general upper bound is proved on the Cartesian product of a path with an arbitrary graph and showed that the bound is tight on thin grids and thin cylinders.

The burning number b(G) of a graph G is used for measuring the speed of contagion in a graph. In this paper, we study the burning number of the generalized Petersen graph P(n, k). We show that for any fixed positive integer k, $$\lim _{n\rightarrow \infty } \frac{b(P(n,k))}{\sqrt{\frac{n}{k}}}=1$$ . Furthermore, we give tight bounds for b(P(n, 1)) and b(P(n, 2)).

The Laplacian spread of a graph G is defined to be the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of G. Let $${\mathcal {Q}}_t(n, d)=\{G\, |\, G-v_0\ \hbox {is a tree on }n-1\hbox { vertices and } d_G(v_0)=d\}.$$ Recently, Y. Xu and J. Meng characterized the unique graph with maximum Laplacian spread among all graphs in the set $${\mathcal {Q}}_t(n, d)$$ with $$1\le d\le (n-4)/2$$ . In this paper, we extend their result by determining the unique graph with maximum Laplacian spread among all graphs in the set $${\mathcal {Q}}_t(n, d)$$ with $$1\le d\le n-5$$ .

Let $$(P,\le )$$ be a partially ordered set with a least element 0. The regular digraph of ideals of P, denoted by $$\overrightarrow{\Gamma }(P)$$ , is a digraph whose vertex-set is the set of all nontrivial ideals of P and, for every two distinct vertices I and J, there is an arc from I to J whenever I contains a nonzero zero-divisor on J. Also, the undirected regular graph of ideals of P, denoted by $$\Gamma (P)$$ , is a graph with all nontrivial ideals of P being the vertex-set, and for two distinct vertices I and J, I is adjacent to J if and only if I contains a nonzero zero-divisor on J or J contains a nonzero zero-divisor on I. In this paper, we study some basic properties of $$\overrightarrow{\Gamma }(P)$$ . Also we completely characterize all posets P with planar regular graph.

Classical topological indices, such as Zagreb indices ( $$M_{1}$$ and $$M_2$$ ) and the well-studied eccentric connectivity index ( $$\xi ^{c}$$ ) directly or indirectly consider the total contribution of all edges in a graph. By considering the total degree sum of all non-adjacent vertex pairs in a graph, Ashrafi et al. (Discrete Appl Math 158:1571–1578, 2010) proposed two new Zagreb-type indices, namely the first Zagreb coindex ( $$\overline{M}_{1}$$ ) and second Zagreb coindex ( $$\overline{M}_{2}$$ ), respectively. Motivated by Ashrafi et al., we consider the total eccentricity sum of all non-adjacent vertex pairs, which we call the eccentric connectivity coindex ( $$\overline{\xi }^{c}$$ ), of a connected graph. In this paper, we study the extremal problems of $$\overline{\xi }^{c}$$ for connected graphs of given order, connected graphs of given order and size, and the trees, unicyclic graphs, bipartite graphs containing cycles and triangle-free graphs of given order, respectively. Additionally, we establish various lower bounds for $$\overline{\xi }^{c}$$ in terms of several other graph parameters.