Maximum Linear Forest of Graphs Resulting from Some Binary Operations

Isagani S. Cabahug Jr. *

Department of Mathematics, College of Arts and Sciences, Central Mindanao University, Musuan, Maramag, Bukidnon, Philippines.

*Author to whom correspondence should be addressed.


For a connected nontrivial graph G, the maximum linear forest of G is the linear forest having maximum number of edges. The number of edges in a maximum linear forest is denoted by \(\ell\)`(G).  In this paper we determine the maximum linear forest of the join and union of nontrivial connected graphs G and H , denoted by G + H and G \(\cup\) H , respectively.

Keywords: Maximum linar forest, join of graphs, union of graphs

How to Cite

Cabahug Jr., I. S. (2023). Maximum Linear Forest of Graphs Resulting from Some Binary Operations. Asian Research Journal of Mathematics, 19(10), 1–6.


Download data is not yet available.


Gross JL, Yellen J. (Eds.). Handbook of graph theory. CRC Press; 2003.

West DB. Introduction to graph theory (Vol. 2). Upper Saddle River: Prentice Hall; 2001.

Harary F. Graph theory (on Demand Printing Of 02787). CRC Press; 2018.

Pelias WP, Jr., ISC. Bipartite domination in some classes of graphs. Asian Research Journal of Mathematics. 2023;19(3):8–17. DOI:

Mangubat DP, Jr., ISC. On the restrained cost eective sets of some special classes of graphs. Asian Research

Journal of Mathematics. 2022;18(8):22–34. DOI:

Consistente LF, Jr., ISC. Hinge total domination on some graph families. Asian Research Journal of

Mathematics. 2022;18(9):25–34. DOI:

Burr SA, Roberts JA. On Ramsey numbers for Linear forests. Discrete Mathematics. 1974;8(3):245-250.

Erdös P, Saks M, Sós VT. Maximum induced trees in graphs. Journal of Combinatorial Theory, Series B.


Faudree RJ, Schelp RH. Ramsey numbers for all linear forests. Discrete Mathematics. 1976;16(2):149-155.

Feige U, Ravi R, Singh M. Short tours through large linear forests. In Integer Programming and

Combinatorial Optimization: 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25,

Proceedings 17. Springer International Publishing. 2014;273-284.

Chartrand G, Zhang P. A first course in graph theory. Courier Corporation; 2013.

Wilson RJ. Introduction to graph theory. Pearson Education India; 1979.