Research article

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

  • 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.

    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:

  • 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.



    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1526) PDF downloads(46) Cited by(0)

Article outline

Figures and Tables

Figures(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog