Zakir DENİZ

A classification of 1-well-covered graphs

A graph is well-covered if all its maximal independent sets have the same size. If a graph is well-covered and remains well-covered upon removal of any vertex, then it is called 1-well-covered graph. It is well-known that ⌊ n 2 ⌋+1 ≤ α(G)+μ(G) ≤ n for any graph G with n vertices where α(G) and μ(G) are the independence and matching numbers of G, respectively. A graph G satisfying α(G) + μ(G) = n is known as König-Egerváry graph, and such graphs are characterized by Levit and Mandrescu [14] under the assumption that G is 1-well-covered. In this paper, we investigate connected 1-well-covered graphs with respect to α(G) + μ(G) = n − k for k ≥ 1 and |G| = n. We further present some combinatorial properties of such graphs. In particular, we provide a tight upper bound on the size of those graphs in terms of k , namely |G| ≤ 10k − 2, also we show that Δ(G) ≤ 2k + 1 and α(G) ≤ min{4k − 1, n − 2k}. This particularly enables us to obtain a characterization of such graphs for k = 1, which settles a problem of Levit and Mandrescu [14].

PDF

___

[1] Berge C. Some common properties for regularizable graphs, edge-critical graphs and b-graphs. Graph Theory and Algorithms 1981; 108-123.
[2] Bıyıkoğlu T, Civan Y. Vertex-decomposable graphs, codismantlability, Cohen-macaulayness, and Castelnuovo- Mumford regularity. The Electronic Journal of Combinatorics 2014; P1-1.
[3] Bourjolly JM, Hammer P, Simeone B. Node-weighted graphs having the König-Egerváry property. Mathematical Programming at Oberwolfach II 1984; 44-63.
[4] Bourjolly JM, Pulleyblank WR. König-Egervary graphs, 2-bicritical graphs and fractional matchings. Discrete Applied Mathematics 1989; 24 (1-3): 63-82.
[5] Campbell S, Ellingham M, Royle G. A characterization of well-covered cubic graphs. Journal of Combinatorial Computing 1993; 13: 193-212.
[6] Chvátal V, Slater PJ. A note on well-covered graphs. Annals of Discrete Mathematics 1993; 55: 179-181.
[7] Demange M, Ekim T. Efficient recognition of equimatchable graphs. Information Processing Letters 2014; 114 (1-2): 66-71.
[8] Deniz Z, Ekim T. Edge-stable equimatchable graphs. Discrete Applied Mathematics 2019; 261: 136-147.
[9] Favaron O. Very well covered graphs. Discrete Mathematics 1982; 42 (2-3): 177-187.
[10] Hartnell B. A characterization of the 1-well-covered graphs with no 4-cycles. Graph Theory in Paris 2006; 219-224.
[11] Hoang DT, Trung TN. A characterization of triangle-free Gorenstein graphs and Cohen-Macaulayness of second powers of edge ideals. Journal of Algebraic Combinatorics 2016; 43 (2): 325-338.
[12] Levit VE, Mandrescu E. On α+ -stable König-Egerváry graphs. Discrete Mathematics 2003; 263 (1-3): 179-190.
[13] Levit VE, Mandrescu E. Critical independent sets and König-Egerváry graphs. Graphs and Combinatorics 2012; 28 (2): 243-250.
[14] Levit VE, Mandrescu E. 1-well-covered graphs revisited. European Journal of Combinatorics 2019; 80: 261-272.
[15] Levit VE, Mandrescu E. On the critical difference of almost bipartite graphs. Journal of Algebraic Combinatorics 2020; 1-15.
[16] Oboudi MR, Nikseresht A. Some combinatorial characterizations of Gorenstein graphs with independence number less than four. Iranian Journal of Science and Technology, Transactions A: Science 2020; 44 (6): 1667-1671.
[17] Paschos VT, Demange M. A generalization of König-Egerváry graphs and heuristics for the maximum independent set problem with improved approximation ratios. European Journal of Operational Research 1997; 97 (3): 580-592.
[18] Pinter MP. Planar regular one-well-covered graphs. Technical report, Vanderbilt University Nashville TN, 1991.
[19] Pinter MP. W2 graphs and strongly well-covered graphs: Two well-covered graph subclasses. Phd, Vanderbilt University, 1992.
[20] Pinter MP. A class of planar well-covered graphs with girth four. Journal of Graph Theory 1995; 19 (1): 69-81.
[21] Pinter MP. A class of well-covered graphs with girth four. Ars Combinatoria 1997; 45: 241-255.
[22] Plummer MD. Some covering concepts in graphs. Journal of Combinatorial Theory 1970; 8 (1): 91-98.
[23] Provan JS, Billera LJ. Decompositions of simplicial complexes related to diameters of convex polyhedra. Mathematics of Operations Research 1980; 5 (4): 576-594.
[24] Sankaranarayana RS, Stewart LK. Complexity results for well-covered graphs. Networks 1992; 22 (3): 247-262.
[25] Staples JAW. On some subclasses of well-covered graphs. Journal of Graph Theory 1979; 3 (2): 197-204.
[26] Tankus D, Tarsi M. Well-covered claw-free graphs. Journal of Combinatorial Theory Series B 1996; 66 (2): 293-302.
[27] Villarreal R. Monomial Algebras. CRC Press, 2018.
[28] West DB. Introduction to Graph Theory, volume 2. Upper Saddle River: Prentice hall, 2001.