Let \(k\ge 1\) be an integer. Let \(G=(V,E)\) be a connected graph with \(n\) vertices and \(m\) edges. Suppose fires break out at two adjacent vertices. In each round, a firefighter can protect \(k\) vertices, and then the fires spread to all unprotected neighbors. For \(uv\in E(G)\), let \(sn_{k}(uv)\) denote the maximum number of vertices the firefighter can save when fires break out at the ends of \(uv\). The \(k\)-edge surviving rate \(\rho'_k(G)\) of \(G\) is defined as the average proportion of vertices saved when the starting vertices of the fires are chosen uniformly at random over all eages, i.e., \(\rho'_k(G)=\sum\limits_{uv\in E(G)}sn_{k}(uv)/nm\). In particular, we write \(\rho'(G)=\rho'_1(G)\). For a given class of graphs \(\mathcal{G}\) and a constant \(\varepsilon>0\), we seek the minimum value \(k\) such that \(\rho'_k(G)>\varepsilon\) for all \(G\in \mathcal{G}\). In this paper, we prove that for Halin graphs, this minimum value is exactly 1. Specifically, every Halin graph \(G\) satisfies \(\rho'(G)> 1/12\).

A bipartite labeling of a tree of order \(n\) is a bijective function that identifies the vertices of \(T\) with the elements of \(\{0, 1, \dots, n-1\}\) in such a way that there exists an integer \(\lambda\) such that the set of labels on the stable sets of \(T\) are \(\{0,1, \dots, \lambda\}\) and {\(\lambda + 1, \lambda +2. \dots, n-1\}.\) The most restrictive and versatile bipartite labeling is the variety called \(\alpha\text{-labeling}\). In this work we present a new construction of \(\alpha\text{-labeled}\) trees where any two adjacent vertices of a path-like tree, or a similar caterpillar, can be amalgamated with selected vertices of two equivalent trees.

A set \(D\) of vertices of a graph \(G=(V_G,E_G)\) is a dominating set of \(G\) if every vertex in \(V_G-D\) is adjacent to at least one vertex in \(D\). The domination number of a graph \(G\), denoted by \(\gamma(G)\), is the cardinality of a smallest dominating set of \(G\). A subset \(D\subseteq V_G\) is called a certified dominating set of \(G\) if \(D\) is a dominating set of \(G\), and every vertex in \(D\) has either zero or at least two neighbours in \(V_G-D\). The cardinality of a smallest certified dominating set of \(G\) is called the certified domination number of \(G\), and it is denoted by \(\gamma_{\rm cer}(G)\). A vertex \(v\) of \(G\) is certified critical if \(\gamma_{\rm cer}(G -v) < \gamma_{\rm cer}(G)\), and a graph \(G\) is vertex certified domination critical or \(\gamma_{cer}\)–critical if the removal of any vertex reduces its certified domination number. In this paper, we give examples and properties of certified critical vertices and vertex certified domination critical graphs. As an example of an application of certified critical vertices, we give a constructive characterisation of trees for which the smaller partite set is a minimum certified dominating set.

In this paper, we consider Ramsey and Gallai-Ramsey numbers for a generalized fan \(F_{t,n}:=K_1+nK_t\) versus triangles. Besides providing some general lower bounds, our main results include the evaluations of \(r(F_{3,2}, K_3)=13\) and \(gr(F_{3,2}, K_3, K_3)=31\).

Seymour’s Second Neighborhood Conjecture (SSNC) asserts that every finite oriented graph has a vertex \(v\) whose second out-neighborhood is at least as large as its first out-neighborhood. Such a vertex is called a Seymour vertex. In this note, we introduce pseudo-Seymour set such that Seymour’s conjecture becomes: Every oriented graph has a singleton pseudo-Seymour set. We prove that any oriented graph has a pseudo-Seymour set \(S\) with \(|S|=2\). Furthermore, we show that there are pseudo-Seymour sets of any size at least 2. We define \(\rho\)-Seymour vertex where \(0 < \rho \leq 1\), and give an approach such that finding \(\rho=1\) is equivalent to the existence of Seymour vertex. Attempting to maximize its value, we prove that for any oriented graph with minimum out-degree \(\delta\), there is \(\rho=\frac{2}{3}(1+\frac{1}{2\delta})\).

In this paper, given a homeomorphism \(f\) of a compact metric space \(X\), we show that the set of all asymptotic average shadowable points of \(f\) is an open and invariant set and \(f\) has the asymptotic average shadowing property if and only if the set of all asymptotic average shadowable points of \(f\) is \(X\) if and only if any Borel probability measure \(\mu\) of \(X\) has the asymptotic average shadowing property.

This paper is concerned with the pullback attractors for the Kirchhoff type BBM equations defined on unbounded domains. Sobolev embeddings are invalid on unbounded domains. We obtain the pullback asymptotic compactness of such non-autonomous BBM equations by using the method of uniform tail-estimates.

We say that a graph \(G\) has a path-system with respect to a set \(W\) of even number of vertices in \(G\) if \(G\) has vertex-disjoint paths \(P_1,P_2, \ldots, P_m\) such that (i) each path \(P_i\) connects two vertices of \(W\) and (ii) the set of end-vertices of the paths \(P_i\) is exactly \(W\). In particular, \(m=|W|/2\). Moreover, if \(G\) has a path-system with respect to every set \(W\) of even number of vertices in \(G\), we say that \(G\) has a path system. We prove the following theorems: (i) if \(G\) is an \(r\)-edge-connected \(r\)-regular graph, then for any \(r-1\) edges \(e_1,\ldots, e_{r-1}\), \(G-\{e_1,\ldots, e_{r-1}\}\) has a path-system, (ii) every \(k\)-connected \(K_{1,k+1}\)-free graph has a path-system, and (iii) if a connected bipartite graph \(G\) with bipartition \((A,B)\) satisfies \(|A| \le 2|B|\), \(|N_G(X)| \ge 2|X|\) or \(N_G(X)=B\) for all \(X\subseteq A\), and \(|N_G(Y)| \ge |Y|\) or \(N_G(Y)=A\) for all \(Y\subseteq B\), then \(G\) has a path-system with respect to every set \(W\) of even number of vertices of \(A\).

For a graph \(G\), an Italian dominating function (IDF) is a function \(f: V(G) \rightarrow \{0,1,2\}\) such that all vertices labeled with 0 must have at least two neighbors assigned the label 1 or at least one neighbor assigned the label 2. The weight of \(f\), denoted by \(w(f)\), is calculated by summing all the labels assigned by the function. Let \(f\) be an IDF on \(G\) with a minimum weight, denoted as \(\gamma_I(G)\). If \(S\) is the set of vertices where \(f(v) > 0\), then an Inverse Italian Dominating Function (IIDF) \(f'\) is defined as an IDF on \(G\) such that \(f'(v) = 0\) for all \(v \in S\). The notation \(\gamma_{iI}(G)\) represents the Inverse Italian Domination Number of the graph \(G\), which is the minimum weight among all IIDFs on \(G\). In this paper, we find \(\gamma_{iI}(G)\) of graphs and characterize the graphs for which \(\gamma_I(G) = 2\) and \(3\), as well as those with \(\gamma_{iI}(G) = 2\) and \(3\). Additionally, we provide a characterization of trees and graphs that achieve the largest possible \(\gamma_{iI}(G)\).

The strongly chordal graph literature has recently expanded to include the sequentially smaller classes of \(s\)-strongly chordal graphs for \(s = 1, 2, 3,\ldots\) (and the limiting class of majorly chordal graphs). These stronger classes preserve — while simultaneously intensifying —  the conventional chords-of-cycles inspiration of chordal graph theory. This leads to characterizing corresponding \(s\)-strongly chordal bipartite graphs and majorly chordal bipartite graphs. Our new analysis does this by using chains of quadrangles, with each adjacent pair of quadrangles having a unique edge in common. This leads to constructive characterizations that exploit a somewhat unexpected resemblance to earlier characterizations of \(s\)-strongly chordal graphs involving chains of triangles sharing common edges to characterize \(s\)-strongly chordal tripartite (and, similarly, multipartite) graphs.

In this paper, we present a method for constructing a new sequence, which we call \(k-\)division sequence and denoted by \(h_n(k)\). Using Fibonacci and Pell sequences, we define the \(k-\)division Fibonacci-Pell sequence obtain its properties, and prove that this sequence is periodic. Then, as an application of the sequence, we define \(1-\)division Fibonacci-Pell sequence on finite groups and study it in the groups \(G_m\) and \(H_{(u,l,m)}\) groups.

We consider the minimum weight and smallest weight minimum-size dominating set problems in vertex-weighted graphs and networks. The latter problem is a two-objective optimization problem, which is different from the classic minimum weight dominating set problem that requires finding a dominating set of the smallest weight in a graph without trying to optimize its cardinality. In other words, the objective of minimizing the size of the dominating set in the two-objective problem can be considered as a constraint, i.e. a particular case of finding Pareto-optimal solutions. First, we show how to reduce the two-objective optimization problem to the minimum weight dominating set problem by using Integer Linear Programming formulations. Then, under different assumptions, the probabilistic method is applied to obtain upper bounds on the minimum weight dominating sets in graphs. The corresponding randomized algorithms for finding small-weight dominating sets in graphs are described as well. Computational experiments are used to illustrate the results for two different types of random graphs.

Let \(G\) be a plane graph. If two edges are adjacent and consecutive on the boundary walk of a face of \(G\), then they are said to be facially adjacent. We call \(G\) facially entire \(k\)-colorable if there is a mapping from \(V(G)\cup E(G)\cup F(G)\) to a \(k\) color set so that any two facially adjacent edges, adjacent vertices, adjacent faces, and incident elements receive different colors. The facial entire chromatic number of \(G\) is defined to be the smallest integer \(k\) such that \(G\) is facially entire \(k\)-colorable. In 2016, Fabrici, Jendrol’ and Vrbjarová conjectured that every connected, loopless, bridgeless plane graph is facially entire \(7\)-colorable. In this paper, we give a positive answer to this conjecture for \(K_4\)-minor-free graphs. More specifically, we shall prove that every \(K_{4}\)-minor-free graph is facially entire \(7\)-colorable.

The Markov graph of a self-map on a combinatorial tree is a directed graph that encodes the covering relations between edges of the tree under the map. This work explores the dynamical structure of self-maps on trees with weakly connected Markov graphs. The main result of the paper is a complete characterization of self-maps on finite sets that yield weakly connected Markov graphs for all trees. Additionally, we describe the dynamical structure of self-maps whose Markov graphs take specific forms, including complete digraphs, cycles, paths, in-stars, and out-stars.

In this paper, we construct two infinite families of graphs \(G(d,c)\) and \(G^+(d,c)\), where, in both cases, a vertex label is \(x_1x_2\ldots x_c\) with \(x_i\in\{1,2,\ldots, d\}\). We provide a tight lower bound on the metric dimension of \(G^+(d, c)\). Moreover, we give the definition and properties of the supertoken graphs, a generalization of the well-known token graphs. Finally, we provide an upper bound on the metric dimension of supertoken graphs.

Let \(A\) be a commutative ring with nonzero identity and \(n\geq 2\) be a positive integer. With the ring \(R=A\times\cdots\times A\) (\(n\) times), one can associate graphs \(TD(R)\) and \(ZD(R)\) respectively called the total dot product graph and the zero-divisor dot product graph of \(R\). In this paper, we study some topological properties of these two dot product graphs of \(R.\) In particular, it is shown that, the zero-divisor dot product graph \(ZD(R)\) is a projective graph if and only if \(R\) is isomorphic to \(\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\) Moreover, we prove that no total dot product graph can be projective. With these observations, we classify all commutative rings for which dot product graphs \(ZD(R)\) and \(TD(R)\) have crosscap two.