Author: "Grippo, Luciano N." / Database: Supplemental Index - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Grippo, Luciano N."' showing total 6 results

Start Over Author "Grippo, Luciano N." Database Supplemental Index

Author: Grippo, Luciano N., Moyano, Verónica A., Grippo, Luciano N., and Moyano, Verónica A.
Abstract: A graph is called split if its vertex set can be partitioned into a stable set and a clique. In this article, we studied two variants of split graphs. A graph Gis polar if its vertex set can be partitioned into two sets Aand Bsuch that G[A] is a complete multipartite graph and G[B] is a disjoint union of complete graphs. A 2-unipolar graph is a polar graph Gsuch that G[A] is a clique and G[B] is the disjoint union of complete graphs with at most two vertices. We present a minimal forbidden induced subgraph characterization for 2-unipolar graphs. In addition, we show that they can be represented as an intersection of substars of special cacti. Let Gbe a graph class, the G-widthof a graph Gis the minimum positive integer ksuch that there exist kindependent sets N1, … , Nksuch that a set Fof nonedges of G, whose endpoints belong to some Niwith i= 1, … , k, can be added so that the resulting graph G′belongs to G. We say that a graph Gis k-probe-Gif it has G-width at most kand when Gis the class of split graphs it is denominated k-probe-split. We prove that deciding, given a graph Gand a positive integer k, whether Gis a h-probe-split graph for some h≤ kis NP-complete. Besides, a characterization by minimal forbidden induced subgraphs for 2-probe-split cographs is presented.
Published: 2024
Full Text: View/download PDF

Author: Grippo, Luciano N., Safe, Martín D., da Silva, Celso M., Del-Vecchio, Renata R., and Dratman, Ezequiel
Subjects: GRAPH connectivity, MATRICES (Mathematics), DISTANCES, EUCLIDEAN distance
Abstract: Let G be a connected graph with vertex set V = { v 1 ,..., v n }. The distance d (v i , v j) between two vertices v i and v j is the number of edges of a shortest path linking them. The distance matrix of G is the n × n matrix such that its (i , j)-entry is equal to d (v i , v j). A formula to compute the determinant of this matrix in terms of the number of vertices was found when the graph either is a tree or is a unicyclic graph. For a byciclic graph, the determinant is known in the case where the cycles have no common edges. In this paper, we present some advances for the remaining cases; i.e., when the cycles share at least one edge. We also present a conjecture for the unsolved cases. [ABSTRACT FROM AUTHOR]
Published: 2019
Full Text: View/download PDF

Author: Allem, L. Emilio, Cafure, Antonio, Dratman, Ezequiel, Grippo, Luciano N., Safe, Martín D., and Trevisan, Vilmar
Abstract: We address the problem of characterizing those graphs G having only one Laplacian eigenvalue greater than or equal to the average degree of G . Our conjecture is that these graphs are stars plus a (possible empty) set of isolated vertices. [ABSTRACT FROM AUTHOR]
Published: 2017
Full Text: View/download PDF

Author: Dourado, Mitre C., Grippo, Luciano N., and Safe, Martín D.
Abstract: We prove several characterizations of hereditary ( p , q )-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs, and show that the recognition of hereditary ( p , q )-Helly hypergraphs can be solved in polynomial time for fixed p but is co-NP-complete if p is part of the input. We also give several characterizations of hereditary ( p , q )-clique-Helly graphs, including one by forbidden induced subgraphs, and prove that the recognition of hereditary ( p , q )-clique-Helly graphs can be solved in polynomial time for fixed p and q but is NP-hard if p or q is part of the input. We prove similar results for hereditary ( p , q )-biclique-Helly graphs. [ABSTRACT FROM AUTHOR]
Published: 2015
Full Text: View/download PDF

Author: Dourado, Mitre C., Durán, Guillermo, Faria, Luerbio, Grippo, Luciano N., and Safe, Martín D.
Subjects: GRAPH theory, MATCHING theory, MATHEMATICAL proofs, SET theory, NUMBER theory, MATHEMATICAL analysis
Abstract: Abstract: A graph has the Kőnig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Kőnig property by forbidden subgraphs, restricted to graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovászʼs result to a characterization of all graphs having the Kőnig property in terms of forbidden configurations (certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the Kőnig property in terms of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. As a consequence of our characterization of graphs with the Kőnig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs. [Copyright &y& Elsevier]
Published: 2011
Full Text: View/download PDF

Author: Durán, Guillermo, Grippo, Luciano N., and Safe, Martín D.
Subjects: TREE graphs, SET theory, DNA, HUMAN gene mapping, HUMAN genome, MATHEMATICAL analysis
Abstract: Abstract: Probe (unit) interval graphs form a superclass of (unit) interval graphs. A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe interval graphs were introduced by Zhang for an application concerning with the physical mapping of DNA in the human genome project. In this work, we present characterizations by minimal forbidden induced subgraphs of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. [Copyright &y& Elsevier]
Published: 2011
Full Text: View/download PDF

Books, media, physical & digital resources

Searchworks