Extremal properties of the bipartite vertex frustration of graphs. (English) Zbl 1234.05134
Summary: The smallest number of vertices that have to be deleted from a graph \(G\) to obtain a bipartite subgraph is called the bipartite vertex frustration of \(G\) and denoted by \(\psi (G)\). In this paper, some extremal properties of this graph invariant are presented. Moreover, we present an exact formula for the bipartite vertex frustration of the corona product of graphs.
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Došlić, T.; Vukičević, D., Computing the bipartite edge frustration of fullerene graphs, Discrete Appl. Math., 155, 1294-1301 (2007) · Zbl 1118.05092 |
| [2] | Došlić, T., Bipartivity of fullerene graphs and fullerene stability, Chem. Phys. Lett., 412, 336-340 (2005) |
| [3] | Erdös, P., On some extremal problems in graph theory, Israel J. Math., 3, 113-116 (1965) · Zbl 0134.43403 |
| [4] | Edwards, C. S., Some extremal properties of bipartite subgraphs, Canad. J. Math., 25, 475-485 (1973) · Zbl 0254.05116 |
| [5] | Cui, Q.; Wang, J., Maximum bipartite subgraphs of cubic triangle-free planar graphs, Discrete Math., 309, 1091-1111 (2009) · Zbl 1167.05038 |
| [6] | Hopkins, G.; Staton, W., Extremal bipartite subgraphs of cubic triangle-free graphs, J. Graph Theory, 6, 115-121 (1982) · Zbl 0486.05036 |
| [7] | Bondy, J. A.; Locke, S. C., Largest bipartite subgraphs in triangle-free graphs with maximum degree three, J. Graph Theory, 10, 477-504 (1986) · Zbl 0609.05046 |
| [8] | Yarahmadi, Z.; Došlić, T.; Ashrafi, A. R., The bipartite edge frustration of composite graphs, Discrete Appl. Math., 158, 1551-1558 (2010) · Zbl 1215.05094 |
| [9] | Yarahmadi, Z., The bipartite edge frustration of extension of splice and link graphs, Appl. Math. Lett., 23, 1077-1081 (2010) · Zbl 1210.05115 |
| [10] | Ghojavand, M.; Ashrafi, A. R., Computing the bipartite edge frustration of some nanotubes, Digest J. Nanomaterials and Biostructures, 3, 209-214 (2008) |
| [11] | Fomin, F.; Gaspers, S.; Pyatkin, A., Finding a minimum feedback vertex set in time O(1.7548n), (IWPEC. IWPEC, Lecture Notes in Comput. Sci., vol. 4169 (2006), Springer), 184-191 · Zbl 1154.05327 |
| [12] | Raman, V.; Saurabh, S.; Subramanian, C., Faster fixed parameter tractable algorithms for finding feedback vertex sets, ACM Trans. Algorithms, 2, 403-415 (2006) · Zbl 1321.05275 |
| [13] | Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading MA · Zbl 0797.05064 |
| [14] | West, D. B., Introduction to Graph Theory (1996), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ · Zbl 0845.05001 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
