Maximum induced forests of product graphs

DOI10.1007/S40840-022-01409-7MaRDI QIDQ2683145zbMATH OpenOpenAlexFDO

Authors Tao Wang, Baoyindureng Wu

Publication date 3 February 2023

Published in Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s40840-022-01409-7

zbMATH Keywords

Cartesian productdirect productforest number of a graphlexicographic product

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph operations (line graphs, products, etc.) (05C76)

Review text

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.

Recommendations

• The Forest Number of (n,m)-Graphs
• The forest number in several classes of regular graphs
• On the maximum orders of an induced forest, an induced tree, and a stable set
• Large induced forests in graphs
• Independence in direct-product graphs

Cites work

• A better bound on the largest induced forests in triangle-free planar graph
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• A new formula for the decycling number of regular graphs
• A note on acyclic number of planar graphs
• Decycling Cartesian Products of Two Cycles
• Decycling graphs
• Decycling sets in certain Cartesian product graphs with one factor complete
• Feedback vertex set in hypercubes
• Graph theory
• Handbook of product graphs
• scientific article; zbMATH DE number 2186982 (Why is no real title available?)
• Independence numbers of product graphs
• Induced forests in bipartite planar graphs
• Large induced forests in graphs
• Large induced forests in planar graphs with girth 4
• Minimum size of feedback vertex sets of planar graphs of girth at least five
• Size of the largest induced forest in subcubic graphs of girth at least four and five
• The chromatic number and other functions of the lexicographic product
• Topics in graph theory. Graphs and their Cartesian product

Cited in

(8)

• On maximum induced forests in graphs
• Product dimension of forests and bounded treewidth graphs
• The forest number in several classes of regular graphs
• The Forest Number of (n,m)-Graphs
• On decycling and forest numbers of Cartesian products of trees
• Characterizing the extremal k-girth graphs on feedback vertex set
• On maximum induced forests of the balanced bipartite graphs
• Some combinatorial algorithms on the eliminating edge feedback number of hypergraphs

This page was built for publication: Maximum induced forests of product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2683145)