A note on PM-compact $ K_4 $-free bricks

Jinqiu Zhou; Qunfang Li; Jinqiu Zhou; Qunfang Li

doi:10.3934/math.2022201

AIMS Mathematics

2022, Volume 7, Issue 3: 3648-3652. doi: 10.3934/math.2022201

Previous Article Next Article

Research article

A note on PM-compact $ K_4 $-free bricks

Jinqiu Zhou ^{1
,
,},
Qunfang Li ²

1.
Faculty of Science, Jiangxi University of Science and Technology, Ganzhou 341000, China
2.
Department of Mathematics, Ganzhou Teachers College, Ganzhou 341000, China

Received: 17 September 2021 Accepted: 25 November 2021 Published: 06 December 2021
MSC : 05C70, 05C75

A 3-connected graph is a brick if the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of the matching covered graphs. Lovász (Combinatorica, 3 (1983), 105-117) showed that every brick is $ K_4 $-based or $ \overline{C}_6 $-based. A brick is $ K_4 $-free (respectively, $ \overline{C}_6 $-free) if it is not $ K_4 $-based (respectively, $ \overline{C}_6 $-based). Recently, Carvalho, Lucchesi and Murty (SIAM Journal on Discrete Mathematics, 34(3) (2020), 1769-1790) characterised the PM-compact $ \overline{C}_6 $-free bricks. In this note, we show that, by using the brick generation procedure established by Norine and Thomas (J Combin Theory Ser B, 97 (2007), 769-817), the only PM-compact $ K_4 $-free brick is $ \overline{C}_6 $, up to multiple edges.
- matching covered graph,
- perfect matching and brick
Citation: Jinqiu Zhou, Qunfang Li. A note on PM-compact $ K_4 $-free bricks[J]. AIMS Mathematics, 2022, 7(3): 3648-3652. doi: 10.3934/math.2022201

Related Papers:

Abstract

A 3-connected graph is a brick if the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of the matching covered graphs. Lovász (Combinatorica, 3 (1983), 105-117) showed that every brick is $ K_4 $-based or $ \overline{C}_6 $-based. A brick is $ K_4 $-free (respectively, $ \overline{C}_6 $-free) if it is not $ K_4 $-based (respectively, $ \overline{C}_6 $-based). Recently, Carvalho, Lucchesi and Murty (SIAM Journal on Discrete Mathematics, 34(3) (2020), 1769-1790) characterised the PM-compact $ \overline{C}_6 $-free bricks. In this note, we show that, by using the brick generation procedure established by Norine and Thomas (J Combin Theory Ser B, 97 (2007), 769-817), the only PM-compact $ K_4 $-free brick is $ \overline{C}_6 $, up to multiple edges.

References

[1]	J. A. Bondy, U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, Springer, New York, 2008.
[2]	M. H. de Carvalho, N. Kothari, X. Wang Y. Lin, Birkhoff-von neumann graphs that are pm-compact, SIAM J. Discrete Math., 34 (2020), 1769–1790. doi: 10.1137/18M1202347 doi: 10.1137/18M1202347
[3]	M. H. de Carvalho, C. L. Lucchesi U. S. R. Murty, How to build a brick, Discrete Math., 306 (2006), 2383–2410. doi: 10.1016/j.disc.2005.12.032 doi: 10.1016/j.disc.2005.12.032
[4]	M. H. de Carvalho, C. L. Lucchesi U. S. R. Murty, On tight cuts in matching covered graphs, J. Comb., 9 (2018), 163–184. doi: 10.4310/JOC.2018.v9.n1.a8 doi: 10.4310/JOC.2018.v9.n1.a8
[5]	M. H. de Carvalho, C. L. Lucchesi U. S. R. Murty, Generating simple bricks and braces, Technical Report IC-08-16, Institute of Computing, University of Campinas, July 2008.
[6]	J. Edmonds, L. Lovász W. R. Pulleyblank, Brick decompositions and the matching rank of graphs, Combinatorica, 2 (1982), 247–274. doi: 10.1007/BF02579233 doi: 10.1007/BF02579233
[7]	N. Kothari, U. S. R. Murty, ${K}_4$-free and $\overline{C}_6$-free planar matching covered graphs, J. Graph Theor., 82 (2016), 5–32. doi: 10.1002/jgt.21882 doi: 10.1002/jgt.21882
[8]	L. Lovász, Matching structure and the matching lattice, Journal of Combinatorial Theory, Series B, 43 (1987), 187–222. doi: 10.1016/0095-8956(87)90021-9 doi: 10.1016/0095-8956(87)90021-9
[9]	L. Lovász, M. D. Plummer, Matching theory, AMS Chelsea Publishing, Providence, RI, 2009.
[10]	S. Norine, R. Thomas, Generating bricks, J. Comb. Theory B, 97 (2007), 769–817. doi: 10.1016/j.jctb.2007.01.002 doi: 10.1016/j.jctb.2007.01.002
[11]	Z. Szigeti, Perfect matchings versus odd cuts, Combinatorica, 22 (2002), 575–589. doi: 10.1007/s00493-002-0008-6 doi: 10.1007/s00493-002-0008-6
[12]	X. Wang, Y. Lin, M. H. de Carvalho, C. L. Lucchesi, G. Sanjith C. H. C. Little, A characterization of PM-compact bipartite and near-bipartite graphs, Discrete Math., 313 (2013), 772–783. doi: 10.1016/j.disc.2012.12.015 doi: 10.1016/j.disc.2012.12.015
[13]	X. Wang, W. Shang, Y. Lin M. H. de Carvalho, A characterization of PM-compact claw-free cubic graphs, Discrete Math. Algorithm. Appl., 6 (2014), 1450025. doi: 10.1142/S1793830914500256 doi: 10.1142/S1793830914500256
[14]	X. Wang, J. Yuan Y. Lin, A characterization of PM-compact hamiltonian bipartite graphs, Acta Math. Appl. Sin. Engl. Ser., 31 (2015), 313–324. doi: 10.1007/s10255-015-0475-3 doi: 10.1007/s10255-015-0475-3

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)