Let \(G\) be an undirected graph. An orientation \(\vec G\) of \(G\) is a directed graph in which every edge of \(G\) is assigned a direction. Directed graph burning is an iterative graph exploration process in which each round consists of two phases: spreading, then vertex selection. Each vertex is initially considered unburned. In the spreading phase, each burned vertex burns all of its out-neighbors. In the vertex selection phase, a vertex is chosen and burned. The burning number of a directed graph \(b(\vec G)\) is the minimum number of rounds necessary to burn all vertices of \(G\). The orientable burning number of an undirected graph \(G\), denoted \(B(G)\), is the maximum burning number across all orientations of \(G\). In this paper, we prove two main results. First, for any integer \(k\) between the minimum and maximum burning numbers of orientations of \(G\), there exists an orientation \(\vec G\) such that \(b(\vec G) = k\). We also determine the orientable burning number of wheels using a bound on the join of directed graphs.

A gap-\([q]\)-vertex labelling of a graph \(G\) is an assignment \(f:V(G)\to\{1,\ldots,q\}\) for which the gap between the largest and smallest labels in the neighbourhood of each vertex induces a proper vertex colouring. The minimum such \(q\) is the vertex-gap number \(\chi_v^g(G)\). We investigate this parameter for generalized Petersen graphs \(P(n,k)\). First, we prove that every bipartite generalized Petersen graph, equivalently every \(P(n,k)\) with \(n\) even and \(k\) odd, has vertex-gap number \(2\); this gives a complete characterization of the generalized Petersen graphs admitting a gap-\([2]\)-vertex labelling. We then construct explicit gap-\([3]\)-vertex labellings for several non-bipartite classes, including families determined by congruence conditions modulo \(4\), \(5\), and \(10\), the family \(n=2tk\) with even \(k\), the cases \(k=1\) and \(k=2\) for specified odd orders, and the family \(n=3k\) with \(k\geq3\). In each case the lower bound follows from the chromatic number, while the upper bound is established by an explicit labelling and a verification of the induced colours on the three edge types of \(P(n,k)\). The results support a natural conjecture that, apart from the exceptional graphs \(P(3,1)\) and \(P(6,2)\), every non-bipartite generalized Petersen graph has vertex-gap number \(3\).

Hartnell and Rall recently introduced the domatic number game. Alice and Bob color the vertices of a graph from a palette [\(k\)], and Alice wins if every color class is a dominating set at the end of the game. The largest winning palette size is denoted by \(\mathop{\mathrm{dom}}\nolimits_{g}(G)\) when Alice moves first and by \(\mathop{\mathrm{dom}}\nolimits’_{g}(G)\) when Bob moves first. Hartnell and Rall asked how these parameters behave under edge and vertex removal, and they also asked whether Bob can win with \(k\) colors while Alice wins with \(k+1\) colors. We give short answers. First, Alice-winning palettes are downward closed: if Alice can win with \(k+1\) colors, then she can win with \(k\) colors, in both versions of the game. Thus the proposed palette-size pathology never occurs. Second, if \(H\) is a spanning subgraph of \(G\), then
\[
\mathop{\mathrm{dom}}\nolimits_{g}(H)\le \mathop{\mathrm{dom}}\nolimits_{g}(G),\qquad \mathop{\mathrm{dom}}\nolimits’_{g}(H)\le \mathop{\mathrm{dom}}\nolimits’_{g}(G).
\]
Thus edge deletion can never increase either invariant, and the inequalities may be strict. Finally, vertex deletion is not monotone: it can increase or decrease either invariant. Deleting one vertex can even increase either invariant by an arbitrarily large amount.

For a graph \(G\) on \(n\) vertices, denote by \(a(G)\) the number of vertices in the largest induced forest in \(G\). The Albertson-Berman conjecture, which has been open since 1979, states that \(a(G) \geq \frac{n}{2}\) for every simple planar graph \(G\). We show that the version of this problem for multigraphs (allowing parallel edges) is easily reduced to the problem about the independence number of simple planar graphs. Specifically, we prove that \(a(M) \geq \frac{n}{4}\) for every planar multigraph \(M\) and that this lower bound is tight. Then, we study the case when the number of pairs of vertices with parallel edges, which we denote by \(k\), is small. In particular, we prove the lower bound \(a(M) \geq \frac{2}{5}n-\frac{k}{10}\) and that the Albertson-Berman conjecture for simple graphs, assuming that it holds, would imply the lower bound \(a(M) \geq \frac{n-k}{2}\) for multigraphs, which would be better than the general lower bound when \(k\) is small. Finally, we study the variant of the problem where the plane multigraphs are prohibited from having \(2\)-faces, which is the main non-trivial problem that we introduce in this article. For that variant without \(2\)-faces, we prove the lower bound \(a(M) \geq \frac{3}{10}n+\frac{7}{30}\) and give a construction of an infinite sequence of multigraphs with \(a(M)=\frac{3}{7}n+\frac{4}{7}\).

A graph \(G\) is said to be a an interval graph, if for each vertex \(u\) of \(G\), one can assign a set \(A_u\) which is a finite union of intervals on the real line such that \(u\) is adjacent to \(v\) in \(G\) if and only if \(A_u\cap A_v\neq\varnothing\). In this paper, we introduce a class of intersection graphs and show that it is equivalent to the class of interval graphs. We also investigate interval numbers of certain intersection graphs and establish several related results.

For a graph \(G=(V(G), E(G))\), a subset \(S \subset V(G)\) is a bipartite dominating set if every vertex in \(G-S\) is adjacent to a vertex in \(S\), and if the subgraph of \(G\) induced by \(S\) is bipartite. The bipartite domination number of \(G\), denoted by \(\gamma_{bip}(G)\), is the minimum cardinality of all bipartite dominating sets of \(G\). Xi and Yue [4] claimed that for every 2-connected outerplanar \(n\)-vertex graph \(G\), \(\gamma_{bip}(G) \leq \lceil \frac n 3 \rceil\), and that this bound is sharp. In this paper, correcting the result, we prove that \(\gamma_{bip}(G) \leq \lceil \frac 38 n \rceil\), where this bound is sharp.

In this article, we obtain the determining number and the metric dimension of the zero-divisor graph of the ring of integers modulo \(n\) and of non-Boolean semisimple rings. For Boolean rings, an upper bound for these parameters is established. While the determining number and metric dimension of \(\Gamma(\mathbb{Z}_n)\) are known in the literature, we provide an alternative derivation based on a structural decomposition of the graph via generalized join. This approach offers a direct and unified method to compute these parameters. Further, we determine these parameters for joins of vertex-transitive graphs and investigate certain questions concerning the relationship between determining number and metric dimension.

Motivated from the concept of strong regularity in the graph theory, few varieties of definitions for strongly regular signed graphs have been introduced. The initial one, which is due to Zaslavsky and the others are given by Stanic and Ramezani. The definition given by Stanic covers all the others. In this paper we provide some constructions for each of the definitions.

In this paper, we prove that if a graph does not contain any cycle of length greater than \(4\), then the square of its line graph is perfect. As an application, we give a concise proof of a known result: the strong chromatic index of a bipartite graph that does not contain any cycle of length greater than \(4\) is at most \(\Delta^2\), where \(\Delta\) represents the maximum degree of the graph. This latter result provides a partial affirmative answer to some known conjectures on upper bounds for the strong chromatic index of graphs.

Recently, Luo [3] introduced the Adding–Swapping Mapping Method to provide an alternative and constructive proof of Stanley’s [4] conjecture on perfect square permutations in \(S_n\) and asked whether the method extends to higher powers. In this paper we answer that question in a more limited but precise structural sense. For each fixed \(k\ge 2\), we define the \(k\)-signature \(R_k(w)\) recording the cycle-count vector modulo \(\gcd(m,k)\) in each length \(m\), and we prove a local residue transition law describing how the insertion map \(D_i\) updates the signature once the cycle length of the insertion point is specified. We also prove explicitly that every \(k\)-th power permutation has zero \(k\)-signature, so the signature gives a necessary obstruction to being a \(k\)-th power. This yields a residue-based partition of \(S_n\) that serves as an indexing scheme for insertion updates. We then show that for \(k\ge 3\) the insertion family does not preserve the class of \(k\)-th powers, explaining why the square case is exceptional from the standpoint of Luo’s method. Finally, we include explicit small-\(n\) data for \(k=3,4\) and prove that the density of \(k\)-th powers in \(S_n\) tends to \(0\) as \(n\to\infty\).