A collection U of edges of a graph G is an edge cover of G if every vertex in G is incident with an edge in U. The minimum cardinality of an edge cover of G is called the edge covering number of G. In this paper, we establish some sharp upper bounds for the edge covering number of graphs resulting from the Cartesian product and composition of two connected graphs in terms of the edge covering numbers of the graphs being considered.

edge cover, edge covering number, spanning path indicator

Received: December 1, 2022; Accepted: December 29, 2022; Published: January 9, 2023

How to cite this article: Rosalio G. Artes, Jr., Covering graphs with optimal collection of edges, Advances and Applications in Discrete Mathematics 36 (2023), 85-91. http://dx.doi.org/10.17654/0974165823006

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] R. G. Artes, Jr. and S. R. Canoy, Jr., Vertex and edge cover of graphs: Revisited, Congressus Numerantium 167 (2004), 65-76.
[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
[3] E. L. Lawler, Combinatorial optimization: networks and matroids, Dover Publications, 2001, pp. 222-223.
[4] S. Pemmaraju and S. Skiena, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge, England: Cambridge University Press, 2003, pp. 318.
[5] E. W. Weisstein, Edge Cover, From MathWorld-A Wolfram Web Resource.
https://mathworld.wolfram.com/EdgeCover.html