Bounding cochordal cover number of graphs via vertex stretching

Document Type : Research Paper


‎‎Science and Research Branch‎, ‎Islamic Azad University‎ ‎(IAU)‎, ‎Tehran‎, ‎Iran.


It is shown that when a special vertex stretching is applied to a graph, the cochordal cover number of the graph increases exactly by one, as it happens to its induced matching number and (Castelnuovo-Mumford) regularity. As a consequence, it is shown that the induced matching number and cochordal cover number of a special vertex stretching of a graph G are equal provided G is well-covered bipartite or weakly chordal graph.


Main Subjects

V. E. Alekseev, On the local restrictions effect on the complexity of inding the graph independence number, Combinatorial-Algebraic Methods in Applied Mathematics, 3--13,Gorkiy Univ. Press, Gorkiy, 1983.
V. E. Alekseev, R. Boliac, D. V. Korobitsyn and V. V. Lozin, NP-hard graph problems and boundary classes of graphs, Theoret. Comput. Sci. 389 (2007), no. 1-2, 219--236.
T. Biyikoglu and Y Civan, Bounding Castelnuovo-Mumford regularity of graphs via Lozin's transformation, arXiv:1302.3064.
R. Boliac, K. Cameron and V. V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin. 72 (2004) 241--253.
J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008.
A. H. Busch, F. F. Dragan and R. Sritharan, New min-max theorems for weakly chordal and dually chordal graphs, Combinatorial Optimization and Applications, Part II (WeiliWu and Ovidiu Daescu, eds.) Lecture Notes in Computer Science, vol 6509, Springer,
Berlin 2010.
M. Katzman, Characteristic-independence of Betti numbers of graph ideals, J. Combin. Theory Ser. A 113 (2006), no. 3, 435--454.
D. V. Korobitsyn, On the complexity of determining the domination number in mono-genic classes of graphs, Diskret. Mat. 2 (1990), no. 3, 90--96 (in Russian), Translation in Discrete Math. Appl. 2 (1992), no. 2, 191--199.
D. N. Kozlov, Complexes of directed trees, J. Combin. Theory Ser. A 88 (1999), no. 1, 112--122.
M. Kummini, Regularity, depth and arithmetic rank of bipartite edge ideals, J. Algebraic Combin. 30 (2009), no. 4, 429--445.
V. V. Lozin, On maximum induced matchings in bipartite graphs, Inform. Process. Lett. 81 81 (2002), no. 1, 7--11.
V. V. Lozin and M. Gerber, On the jump number problem in hereditary classes of bipartite graphs, Order 17 (2000), no. 4, 377--385.
R. Woodroofe, Matchings, coverings, and Castelnuovo--Mumford regularity, J. Commut. Algebra 6 (2014), no. 2, 287--304.