×

zbMATH — the first resource for mathematics

On balanced graphs. (English) Zbl 1080.05058
Summary: Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator.
Reviewer: Reviewer (Berlin)

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C17 Perfect graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstee, R., Farber, M.: Characterizations of totally balanced matrices. J. Algorithms 5, 215–230 (1984) · Zbl 0551.05026 · doi:10.1016/0196-6774(84)90028-2
[2] Berge, C.: Les problemes de colorations en théorie des graphes. Publ. Inst. Stat. Univ. Paris 9, 123–160 (1960) · Zbl 0103.16201
[3] Berge, C.: Sur certains hypergraphes généralisant les graphes biparties. In: P. Erdös, A. Rényi, V. Sós (eds.), Combinatorial Theory and Applications. North–Holland, Amsterdam, 1970, pp. 119–133,
[4] Berge, C.: Balanced matrices. Math. Program. 2, 19–31 (1972) · Zbl 0247.05126 · doi:10.1007/BF01584535
[5] Berge, C.: Notes sur les bonnes colorations d’un hypergraphe. Cah. Cent. Etud. Rech. Oper. 15, 219–223 (1973) · Zbl 0272.05128
[6] Berge, C., Las Vergnas, M.: Sur un théorème du type König pour hypergraphes. Ann. N.Y. Acad. Sci. 175, 32–40 (1970) · Zbl 0229.05136
[7] Cameron, K., Edmonds, J.: Existentially polytime theorems. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 1, 83–100 (1990) · Zbl 0726.68062
[8] Chvátal, V.: On certain polytopes associated with graphs. J. Comb. Theory, Ser. B 18, 138–154 (1975) · Zbl 0277.05139 · doi:10.1016/0095-8956(75)90041-6
[9] Conforti, M.: Personal communication. 2004
[10] Conforti, M., Cornuéjols, G., Rao, R.: Decomposition of balanced matrices. J. Comb. Theory, Ser. B 77, 292–406 (1999) · Zbl 1023.05025 · doi:10.1006/jctb.1999.1932
[11] Conforti, M., Cornuéjols, G., Vušković, K.: Balanced matrices. Discrete Math. To appear
[12] Cornuéjols, G.: Combinatorial Optimization: Packing and Covering. SIAM, Philadelphia, 2001 · Zbl 0972.90059
[13] Dahlhaus, E., Manuel, P., Miller, M.: Maximum h-colourable subgraph problem in balanced graphs. Inf. Process. Lett. 65, 301–303 (1998) · Zbl 1338.68098 · doi:10.1016/S0020-0190(98)00019-2
[14] Duchet, P.: Hypergraphs. In: R. Graham, M. Grötschel, L. Lovász (eds.), Handbook of Combinatorics. Elsevier, Amsterdam, 1995, pp. 381–432 · Zbl 0859.05063
[15] Escalante, F.: Über iterierte clique-graphen. Abh. Math. Semin. Univ. Hamb. 39, 59–68 (1973) · Zbl 0266.05116 · doi:10.1007/BF02992818
[16] Farber, M.: Characterizations of strongly chordal graphs. Discrete Math. 43, 173–189 (1983) · Zbl 0514.05048 · doi:10.1016/0012-365X(83)90154-1
[17] Fulkerson, D., Hoffman, A., Oppenheim, R.: On balanced matrices. Math. Program. 1, 120–132 (1974) · Zbl 0357.90038
[18] Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs. Ann. Discrete Math., vol. 57, second edn. North–Holland, Amsterdam, 2004 · Zbl 1050.05002
[19] Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981) · Zbl 0492.90056 · doi:10.1007/BF02579273
[20] Guruswami, V., Pandu Rangan, C.: Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Appl. Math. 100, 183–202 (2000) · Zbl 0948.68135 · doi:10.1016/S0166-218X(99)00159-6
[21] Hamelink, R.: A partial characterization of clique graphs. J. Comb. Theory, Ser. B 5, 192–197 (1968) · Zbl 0167.22203 · doi:10.1016/S0021-9800(68)80055-9
[22] Hopcroft, J., Karp, R.: An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225–231 (1973) · Zbl 0266.05114 · doi:10.1137/0202019
[23] Hsu, W., Nemhauser, G.: Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs. Discrete Math. 37, 181–191 (1981) · Zbl 0473.05049 · doi:10.1016/0012-365X(81)90218-1
[24] Lehel, J., Tuza, Z.: Neighborhood perfect graphs. Discrete Math. 61, 93–101 (1986) · Zbl 0602.05053 · doi:10.1016/0012-365X(86)90031-2
[25] Lubiw, A.: Orderings and some combinatorial optimization problems with geometric applications. Ph.D. thesis, Department of Computer Science, University of Toronto, Toronto, 1985
[26] Prisner, E.: Hereditary clique-Helly graphs. J. Comb. Math. Comb. Comput. 14, 216–220 (1993) · Zbl 0794.05113
[27] Protti, F., Szwarcfiter, J.: Clique-inverse graphs of bipartite graphs. J. Comb. Math. Comb. Comput. 40, 193–203 (2002) · Zbl 0995.05128
[28] Sbihi, N.: Algorithmes de recherche d’un stable de cardinalite maximum dans un graphe sans etoile. Discrete Math. 29, 53–76 (1980) · Zbl 0444.05049 · doi:10.1016/0012-365X(90)90287-R
[29] Szwarcfiter, J.: A survey on Clique Graphs. In: C. Linhares Sales, B. Reed (eds.), Recent Advances in Algorithms and Combinatorics. Springer–Verlag, New York, pp 109–136, 2003 · Zbl 1027.05071
[30] Tsukiyama, S., Idle, M., Ariyoshi, H., Shirakawa, Y.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6 (3), 505–517 (1977) · Zbl 0364.05027 · doi:10.1137/0206036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.