Source author record

Leandro Montero

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Vertex removal in biclique graphs

A \textit{biclique} is a maximal induced complete bipartite subgraph. The \textit{biclique graph} of a graph $H$ , denoted by $KB(H)$ , is the intersection graph of the family of all bicliques of $H$ . In this work we address the following question: Given a biclique graph $G=KB(H)$ , is it possible to remove a vertex $q$ of $G$ , such that $G - \{q\}$ is a biclique graph? And if possible, can we obtain a graph $H'$ such that $G - \{q\} = KB(H')$ ? We show that the general question has a "no" for answer. However, we prove that if $G$ has a vertex $q$ such that $d(q) = 2$ , then $G-\{q\}$ is a biclique graph and we show how to obtain $H'$ .

preprint2016arXiv

Tight lower bounds on the number of bicliques in false-twin-free graphs

A \emph{biclique} is a maximal bipartite complete induced subgraph of $G$ . Bicliques have been studied in the last years motivated by the large number of applications. In particular, enumeration of the maximal bicliques has been of interest in data analysis. Associated with this issue, bounds on the maximum number of bicliques were given. In this paper we study bounds on the minimun number of bicliques of a graph. Since adding false-twin vertices to $G$ does not change the number of bicliques, we restrict to false-twin-free graphs. We give a tight lower bound on the minimum number bicliques for a subclass of $\{C_4$ ,false-twin $\}$ -free graphs and for the class of $\{K_3$ ,false-twin $\}$ -free graphs. Finally we discuss the problem for general graphs.

preprint2015arXiv

Almost every graph is divergent under the biclique operator

A biclique of a graph $G$ is a maximal induced complete bipartite subgraph of $G$ . The biclique graph of $G$ denoted by $KB(G)$ , is the intersection graph of all the bicliques of $G$ . The biclique graph can be thought as an operator between graphs. The iterated biclique graph of $G$ denoted by $KB^{k}(G)$ , is the graph obtained by applying the biclique operator $k$ successive times to $G$ . The associated problem is deciding whether an input graph converges, diverges or is periodic under the biclique operator when $k$ grows to infinity. All possible behaviors were characterized recently and an $O(n^4)$ algorithm for deciding the behavior of any graph under the biclique operator was also given. In this work we prove new structural results of biclique graphs. In particular, we prove that every false-twin-free graph with at least $13$ vertices is divergent. These results lead to a linear time algorithm to solve the same problem.

preprint2014arXiv

Proper Hamiltonian Paths in Edge-Coloured Multigraphs

Given a $c$ -edge-coloured multigraph, a proper Hamiltonian path is a path that contains all the vertices of the multigraph such that no two adjacent edges have the same colour. In this work we establish sufficient conditions for an edge-coloured multigraph to guarantee the existence of a proper Hamiltonian path, involving various parameters as the number of edges, the number of colours, the rainbow degree and the connectivity.

preprint2013arXiv

Further results on strong edge-colourings in outerplanar graphs

An edge-colouring is {\em strong} if every colour class is an induced matching. In this work we give a formulae that determines either the optimal or the optimal plus one strong chromatic index of bipartite outerplanar graphs. Further, we give an improved upper bound for any outerplanar graph which is close to optimal. All our proofs yield efficient algorithms to construct such colourings.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.