Let \(G\) be a \((p,q)\) graph. Let \(f\) be a function from \(V(G)\) to the set \(\{1,2,\ldots, k\}\) where \(k\) is an integer \(2< k\leq \left|V(G)\right|\). For each edge \(uv\) assign the label \(r\) where \(r\) is the remainder when \(f(u)\) is divided by \(f(v)\) (or) \(f(v)\) is divided by \(f(u)\) according as \(f(u)\geq f(v)\) or \(f(v)\geq f(u)\). \(f\) is called a \(k\)-remainder cordial labeling of \(G\) if \(\left|v_{f}(i)-v_{f}(j)\right|\leq 1\), \(i,j\in \{1,\ldots , k\}\) where \(v_{f}(x)\) denote the number of vertices labeled with \(x\) and \(\left|\eta_{e}(0)-\eta_{o}(1)\right|\leq 1\) where \(\eta_{e}(0)\) and \(\eta_{o}(1)\) respectively denote the number of edges labeled with even integers and number of edges labeled with odd integers. A graph with admits a \(k\)-remainder cordial labeling is called a \(k\)-remainder cordial graph. In this paper we investigate the \(4\)-remainder cordial labeling behavior of Prism, Crossed prism graph, Web graph, Triangular snake, \(L_{n} \odot mK_{1}\), Durer graph, Dragon graph.

Given a connected graph \(H\), its first Zagreb index \(M_{1}(H)\) is equal to the sum of squares of the degrees of all vertices in \(H\). In this paper, we give a best possible lower bound on \(M_{1}(H)\) that guarantees \(H\) is \(\tau\)-path-coverable and \(\tau\)-edge-Hamiltonian, respectively. Our research supplies a continuation of the results presented by Feng et al. (2017).

The degree of an edge \(uv\) of a graph \(G\) is \(d_G(u)+d_G(v)-2.\) The degree associated edge reconstruction number of a graph \(G\) (or dern(G)) is the minimum number of degree associated edge-deleted subgraphs that uniquely determines \(G.\) Graphs whose vertices all have one of two possible degrees \(d\) and \(d+1\) are called \((d,d+1)\)-bidegreed graphs. It was proved, in a sequence of two papers [1,17], that \(dern(mK_{1,3})=4\) for \(m>1,\) \(dern(mK_{2,3})=dern(rP_3)=3\) for \(m>0, ~r>1\) and \(dern(G)=1\) or \(2\) for all other bidegreed graphs \(G\) except the \((d,d+1)\)-bidegreed graphs in which a vertex of degree \(d+1\) is adjacent to at least two vertices of degree \(d.\) In this paper, we prove that \(dern(G)= 1\) or \(2\) for this exceptional bidegreed graphs \(G.\) Thus, \(dern(G)\leq 4\) for all bidegreed graphs \(G.\)

A proper total coloring of a graph \( G \) such that there are at least 4 colors on those vertices and edges incident with a cycle of \( G \), is called an acyclic total coloring. The acyclic total chromatic number of \( G \), denoted by \( \chi^{”}_{a}(G) \), is the smallest number of colors such that \( G \) has an acyclic total coloring. In this article, we prove that for any graph \( G \) with \( \Delta(G)=\Delta \) which satisfies \( \chi^{”}(G)\leq A \) for some constant \( A \), and for any integer \( r \), \( 1\leq r \leq 2\Delta \), there exists a constant \( c>0 \) such that if \( g(G)\geq\frac{c\Delta}{r}\log\frac{\Delta^{2}}{r} \), then \( \chi^{”}_{a}(G)\leq A+r \).

We study a discrete-time model for the spread of information in a graph, motivated by the idea that people believe a story when they learn of it from two different origins. Similar to the burning number, in this problem, information spreads in rounds and a new source can appear in each round. For a graph \(G\), we are interested in \(b_2(G)\), the minimum number of rounds until the information has spread to all vertices of graph \(G\). We are also interested in finding \(t_2(G)\), the minimum number of sources necessary so that the information spreads to all vertices of \(G\) in \(b_2(G)\) rounds. In addition to general results, we find \(b_2(G)\) and \(t_2(G)\) for the classes of spiders and wheels and show that their behavior differs with respect to these two parameters. We also provide examples and prove upper bounds for these parameters for Cartesian products of graphs.

An hourglass \(\Gamma_0\) is the graph with degree sequence \(\{4,2,2,2,2\}\). In this paper, for integers \(j\geq i\geq 1\), the bull \(B_{i,j}\) is the graph obtained by attaching endvertices of two disjoint paths of lengths \(i,j\) to two vertices of a triangle. We show that every 3-connected \(\{K_{1,3},\Gamma_0,X\}\)-free graph, where \(X\in \{ B_{2,12},\,B_{4,10},\,B_{6,8}\}\), is Hamilton-connected. Moreover, we give an example to show the sharpness of our result, and complete the characterization of forbidden induced bulls implying Hamilton-connectedness of a 3-connected {claw, hourglass, bull}-free graph.

Let \(G=(V,E)\) be a simple connected graph with vertex set \(V\) and edge set \(E\). The Randić index of graph \(G\) is the value \(R(G)=\sum_{uv\in E(G)} \frac{1}{\sqrt{d(u)d(v)}}\), where \(d(u)\) and \(d(v)\) refer to the degree of the vertices \(u\) and \(v\). We obtain a lower bound for the Randić index of trees in terms of the order and the Roman domination number, and we characterize the extremal trees for this bound.

In this paper, it is pointed out that the definition of `Fibonacci \((p,r)\)-cube’ in many papers (denoted by \(I\Gamma_{n}^{(p,r)}\)) is incorrect. The graph \(I\Gamma_{n}^{(p,r)}\) is not the same as the original one (denoted by \(O\Gamma_{n}^{(p,r)}\)) introduced by Egiazarian and Astola. First, it is shown that \(I\Gamma_{n}^{(p,r)}\) and \(O\Gamma_{n}^{(p,r)}\) have different recursive structure. Then, it is proven that all the graphs \(O\Gamma_{n}^{(p,r)}\) are partial cubes. However, only a small part of graphs \(I\Gamma_{n}^{(p,r)}\) are partial cubes. It is also shown that \(I\Gamma_{n}^{(p,r)}\) and \(O\Gamma_{n}^{(p,r)}\) have different medianicity. Finally, several questions are listed for further investigation.

A \(q\)-total coloring of \(G\) is an assignment of \(q\) colors to the vertices and edges of \(G\), so that adjacent or incident elements have different colors. The Total Coloring Conjecture (TCC) asserts that a total coloring of a graph \(G\) has at least \(\Delta+1\) and at most \(\Delta+2\) colors. In this paper, we determine that all members of new infinite families of snarks obtained by the Kochol superposition of Goldberg and Loupekine with Blowup and Semiblowup snarks are Type~1. These results contribute to a question posed by Brinkmann, Preissmann and D. Sasaki (2015) by presenting negative evidence about the existence of Type~2 cubic graphs with girth at least 5.

In this note, we establish six Gallai theorems involving twelve minority and majority parameters. Accordingly, the complexity problems corresponding to some of these parameters are obtained.