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.

Threshold graphs are graphs whose node set can be partitioned into a clique and an independent set, with the additional property that for each pair of nodes, one’s neighborhood is a subset of the other’s neighborhood. Threshold graphs have been well-studied in graph theory, but not much is known about multigraphs that are underlying threshold. Proper threshold graphs are those in which all nodes in the independent set have the same degree. In this paper, we present a formula for the eigenvalues of a particular class of multigraphs that are underlying proper threshold.