Maximum induced forests of product graphs (Q2683145)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximum induced forests of product graphs |
scientific article |
Statements
Maximum induced forests of product graphs (English)
0 references
3 February 2023
0 references
The forest number \(f(G)\) for a graph \(G\) is the maximum number of vertices in an induced forest of \(G\). A product \(G\ast H\) of graphs \(G\) and \(H\) is a graph on the vertex set \(V(G)\times V(H)\). Based on the definition of an edge set, several products are known. In particular, two vertices \((g,h),(g\prime,h\prime)\in V(G)\times V(H)\) are adjacent in \begin{itemize} \item the Cartesian product \(G\Box H\) if \(g=g\prime\) and \(hh\prime\in E(H)\) or \(gg\prime\in E(G)\) and \(h=h\prime\); \item the direct product \(G\times H\) if \(gg\prime\in E(G)\) and \(hh^\prime\in E(H)\); \item the lexicographic product \(G\circ H\) if \(gg\prime\in E(G)\) or \(g=g\prime\) and \(hh\prime\in E(H)\). \end{itemize} In this paper, the forest number of Cartesian, direct and lexicographic products is studied. Some bounds are given and some conditions on the factors are presented that yield some exact values for the forest number of the mentioned products. The topic remains open for further investigation.
0 references
forest number of a graph
0 references
Cartesian product
0 references
direct product
0 references
lexicographic product
0 references
0 references