Biclique graphs of split graphs. Groshaus, M., Guedes, A., & Puppo, J. Discrete Applied Mathematics, 323:252-267, 2022. LAGOS’19 – X Latin and American Algorithms, Graphs, and Optimization Symposium – Belo Horizonte, Minas Gerais, Brazil![Biclique graphs of split graphs [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex 3 downloads The biclique graph is the intersection graph of the bicliques of a graph. Its recognition problem is still open. In this paper we study the problem restricted to the class of split graphs. We define a class called nested separable split graphs and solve the recognition problem of biclique graphs of a subclass of the mentioned class. For that, we give a polynomial time algorithm with positive certificate. We also characterize nested split graphs and study properties of biclique graphs of split graphs. For example, we show that they are Hamiltonian. We also present a complexity result for recognizing graphs such that their biclique graphs are complete graphs, that is, we prove that the problem of recognizing biclique-complete graphs in co-NP-complete.
@article{GroshausGuedesPuppo2022,
title = {Biclique graphs of split graphs},
journal = {Discrete Applied Mathematics},
volume = {323},
pages = {252-267},
year = {2022},
issn = {0166-218X},
doi = {https://doi.org/10.1016/j.dam.2021.12.028},
url = {https://www.sciencedirect.com/science/article/pii/S0166218X2100514X},
author = {M. Groshaus and A.L.P. Guedes and J.P. Puppo},
keywords = {Bicliques, Biclique graphs, Split graphs, Biclique-complete, -complete},
note = {LAGOS’19 – X Latin and American Algorithms, Graphs, and Optimization Symposium – Belo Horizonte, Minas Gerais, Brazil},
abstract = {The biclique graph is the intersection graph of the bicliques of a graph. Its recognition problem is still open. In this paper we study the problem restricted to the class of split graphs. We define a class called nested separable split graphs and solve the recognition problem of biclique graphs of a subclass of the mentioned class. For that, we give a polynomial time algorithm with positive certificate. We also characterize nested split graphs and study properties of biclique graphs of split graphs. For example, we show that they are Hamiltonian. We also present a complexity result for recognizing graphs such that their biclique graphs are complete graphs, that is, we prove that the problem of recognizing biclique-complete graphs in co-NP-complete.}
}
Downloads: 3
{"_id":"Ei9sRjXTrR4gPRGrK","bibbaseid":"groshaus-guedes-puppo-bicliquegraphsofsplitgraphs-2022","author_short":["Groshaus, M.","Guedes, A.","Puppo, J."],"bibdata":{"bibtype":"article","type":"article","title":"Biclique graphs of split graphs","journal":"Discrete Applied Mathematics","volume":"323","pages":"252-267","year":"2022","issn":"0166-218X","doi":"https://doi.org/10.1016/j.dam.2021.12.028","url":"https://www.sciencedirect.com/science/article/pii/S0166218X2100514X","author":[{"firstnames":["M."],"propositions":[],"lastnames":["Groshaus"],"suffixes":[]},{"firstnames":["A.L.P."],"propositions":[],"lastnames":["Guedes"],"suffixes":[]},{"firstnames":["J.P."],"propositions":[],"lastnames":["Puppo"],"suffixes":[]}],"keywords":"Bicliques, Biclique graphs, Split graphs, Biclique-complete, -complete","note":"LAGOS’19 – X Latin and American Algorithms, Graphs, and Optimization Symposium – Belo Horizonte, Minas Gerais, Brazil","abstract":"The biclique graph is the intersection graph of the bicliques of a graph. Its recognition problem is still open. In this paper we study the problem restricted to the class of split graphs. We define a class called nested separable split graphs and solve the recognition problem of biclique graphs of a subclass of the mentioned class. For that, we give a polynomial time algorithm with positive certificate. We also characterize nested split graphs and study properties of biclique graphs of split graphs. For example, we show that they are Hamiltonian. We also present a complexity result for recognizing graphs such that their biclique graphs are complete graphs, that is, we prove that the problem of recognizing biclique-complete graphs in co-NP-complete.","bibtex":"@article{GroshausGuedesPuppo2022,\ntitle = {Biclique graphs of split graphs},\njournal = {Discrete Applied Mathematics},\nvolume = {323},\npages = {252-267},\nyear = {2022},\nissn = {0166-218X},\ndoi = {https://doi.org/10.1016/j.dam.2021.12.028},\nurl = {https://www.sciencedirect.com/science/article/pii/S0166218X2100514X},\nauthor = {M. Groshaus and A.L.P. Guedes and J.P. Puppo},\nkeywords = {Bicliques, Biclique graphs, Split graphs, Biclique-complete, -complete},\nnote = {LAGOS’19 – X Latin and American Algorithms, Graphs, and Optimization Symposium – Belo Horizonte, Minas Gerais, Brazil},\nabstract = {The biclique graph is the intersection graph of the bicliques of a graph. Its recognition problem is still open. In this paper we study the problem restricted to the class of split graphs. We define a class called nested separable split graphs and solve the recognition problem of biclique graphs of a subclass of the mentioned class. For that, we give a polynomial time algorithm with positive certificate. We also characterize nested split graphs and study properties of biclique graphs of split graphs. For example, we show that they are Hamiltonian. We also present a complexity result for recognizing graphs such that their biclique graphs are complete graphs, that is, we prove that the problem of recognizing biclique-complete graphs in co-NP-complete.}\n}\n\n","author_short":["Groshaus, M.","Guedes, A.","Puppo, J."],"key":"GroshausGuedesPuppo2022","id":"GroshausGuedesPuppo2022","bibbaseid":"groshaus-guedes-puppo-bicliquegraphsofsplitgraphs-2022","role":"author","urls":{"Paper":"https://www.sciencedirect.com/science/article/pii/S0166218X2100514X"},"keyword":["Bicliques","Biclique graphs","Split graphs","Biclique-complete","-complete"],"metadata":{"authorlinks":{}},"downloads":3},"bibtype":"article","biburl":"http://www.inf.ufpr.br/andre/bibtex/meus.bib","dataSources":["8EF7A9sBtzR7yAc4T","wKyTDzPCLmTgMwZxK","56qKgLT3Qtqzn3c7B"],"keywords":["bicliques","biclique graphs","split graphs","biclique-complete","-complete"],"search_terms":["biclique","graphs","split","graphs","groshaus","guedes","puppo"],"title":"Biclique graphs of split graphs","year":2022,"downloads":3}