Source author record

Guillermo Durán

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

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

2-nested matrices: towards understanding the structure of circle graphs

A $(0,1)$ -matrix has the consecutive-ones property (C1P) if its columns can be permuted to make the $1$ 's in each row appear consecutively. This property was characterised in terms of forbidden submatrices by Tucker in 1972. Several graph classes were characterised by means of this property, including interval graphs and strongly chordal digraphs. In this work, we define and characterise 2-nested matrices, which are $(0,1)$ -matrices with a variant of the C1P and for which there is also certain assignment of one of two colors to each block of consecutive $1$ 's in each row. The characterization of 2-nested matrices in the present work is of key importance to characterise split graphs that are also circle by minimal forbidden induced subgraphs.

preprint2016arXiv

Neighborhood covering and independence on two superclasses of cographs

Given a simple graph $G$ , a set $C \subseteq V(G)$ is a neighborhood cover set if every edge and vertex of $G$ belongs to some $G[v]$ with $v \in C$ , where $G[v]$ denotes the subgraph of $G$ induced by the closed neighborhood of the vertex $v$ . Two elements of $E(G) \cup V(G)$ are neighborhood-independent if there is no vertex $v\in V(G)$ such that both elements are in $G[v]$ . A set $S\subseteq V(G)\cup E(G)$ is neighborhood-independent if every pair of elements of $S$ is neighborhood-independent. Let $ρ_{\mathrm n}(G)$ be the size of a minimum neighborhood cover set and $α_{\mathrm n}(G)$ of a maximum neighborhood-independent set. Lehel and Tuza defined neighborhood-perfect graphs $G$ as those where the equality $ρ_{\mathrm n}(G') = α_{\mathrm n}(G')$ holds for every induced subgraph $G'$ of $G$ . In this work we prove forbidden induced subgraph characterizations of the class of neighborhood-perfect graphs, restricted to two superclasses of cographs: $P_4$ -tidy graphs and tree-cographs. We give as well linear-time algorithms for solving the recognition problem of neighborhood-perfect graphs and the problem of finding a minimum neighborhood cover set and a maximum neighborhood-independent set in these same classes.

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.