Maximum induced forests of product graphs. (English) Zbl 1508.05084
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
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.
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
- ●
- 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\);
- ●
- the direct product \(G\times H\) if \(gg\prime\in E(G)\) and \(hh^\prime\in E(H)\);
- ●
- the lexicographic product \(G\circ H\) if \(gg\prime\in E(G)\) or \(g=g\prime\) and \(hh\prime\in E(H)\).
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.
Reviewer: Iztok Peterin (Maribor)
MSC:
| 05C30 | Enumeration in graph theory |
| 05C05 | Trees |
| 05C76 | Graph operations (line graphs, products, etc.) |
References:
| [1] | Beineke, LW; Vandell, RC, Decycling graphs, J. Graph Theory, 25, 59-77 (1997) · Zbl 0870.05033 · doi:10.1002/(SICI)1097-0118(199705)25:1<59::AID-JGT4>3.0.CO;2-H |
| [2] | Bondy, JA; Murty, USR, Graph Theory. Graduate Texts in Mathematics (2008), New York: Springer, New York · Zbl 1134.05001 |
| [3] | Dross, F.; Montassier, M.; Pinlou, A., Large induced forests in planar graphs with girth 4, Discrete Appl. Math., 254, 96-106 (2019) · Zbl 1404.05036 · doi:10.1016/j.dam.2018.06.029 |
| [4] | Dross, F.; Montassier, M.; Pinlou, A., A lower bound on the order of the largest induced forest in planar graphs with high girth, Discrete Appl. Math., 214, 99-107 (2016) · Zbl 1346.05039 · doi:10.1016/j.dam.2016.06.011 |
| [5] | Focardi, FL; Luccio, D., Peleg, Feedback vertex set in hypercubes, Inform. Process. Lett., 76, 1-5 (2000) · Zbl 1338.68218 · doi:10.1016/S0020-0190(00)00127-7 |
| [6] | Geller, D.; Stahl, S., The chromatic number and other functions of the lexicographic product, J. Combin. Theory Ser. B., 19, 87-95 (1975) · Zbl 0282.05114 · doi:10.1016/0095-8956(75)90076-3 |
| [7] | Hartnell, BL; Whitehead, CA, Decycling sets in certain Cartesian product graphs with one factor complete, Australas. J. Combin., 40, 305-315 (2008) · Zbl 1163.05028 |
| [8] | Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs (2011), Boca Raton: CRC Press, Taylor Francis Group, Boca Raton · Zbl 1283.05001 · doi:10.1201/b10959 |
| [9] | Imrich, W.; Klavžar, S.; Rall, D., Topics in Graph Theory. Graphs and Their Cartesian Product (2008), Wellesley: A K Peters Ltd, Wellesley · Zbl 1156.05001 · doi:10.1201/b10613 |
| [10] | Jha, PK; Slutzki, G., Independence numbers of product graphs, Appl. Math. Lett., 7, 91-94 (1994) · Zbl 0811.05033 · doi:10.1016/0893-9659(94)90018-3 |
| [11] | Kelly, T.; Liu, C-H, Minimum size of feedback vertex sets of planar graphs of girth at least five, Eur. J. Combin., 61, 138-150 (2017) · Zbl 1352.05057 · doi:10.1016/j.ejc.2016.10.009 |
| [12] | Kelly, T.; Liu, C-H, Size of the largest induced forest in subcubic graphs of girth at least four and five, J. Graph Theory, 89, 457-478 (2018) · Zbl 1473.05144 · doi:10.1002/jgt.22361 |
| [13] | Le, H., A better bound on the largest induced forests in triangle-free planar graphs, Graphs Combin., 34, 1217-1246 (2018) · Zbl 1402.05047 · doi:10.1007/s00373-018-1944-2 |
| [14] | Petruševski, M.; Škrekovski, R., A note on acyclic number of planar graphs, ARS Math. Contemp., 13, 317-322 (2017) · Zbl 1380.05040 · doi:10.26493/1855-3974.1118.143 |
| [15] | Pike, DA; Zou, Y., Decycling Cartesian products of two cycles, SIAM J. Discrete Math., 19, 651-663 (2005) · Zbl 1096.05030 · doi:10.1137/S089548010444016X |
| [16] | Punnim, N., Decycling regular graphs, Australas. J. Combin., 32, 147-162 (2005) · Zbl 1070.05030 |
| [17] | Ren, H.; Yang, C.; Zhao, T., A new formula for the decycling number of regular graphs, Discrete Math., 340, 12, 3020-3031 (2017) · Zbl 1370.05105 · doi:10.1016/j.disc.2017.07.011 |
| [18] | Shi, L.; Xu, H., Large induced forests in graphs, J. Graph Theory, 85, 759-779 (2017) · Zbl 1368.05034 · doi:10.1002/jgt.22104 |
| [19] | Wang, Y.; Xie, Q.; Yu, X., Induced forests in bipartite planar graphs, J. Comb., 8, 93-166 (2017) · Zbl 1352.05053 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
