Erica G. Hinrichsen

dblp:148/6194 · DBLP profile ↗
← Back
4ranked-venue papers
1as first author
1since 2021 · last 2023
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 4 · 1 first-author · 1 since 2021Artificial intelligence and machine learning · 1Databases, data management, data science and information retrieval · 1 · 1 first-author
YearPublicationVenuePosition
2023 Characterization of graphs with perfect closed neighbourhood matrices
abstract
The main purpose of this work is to characterize the graphs whose closed neighbourhood matrices are perfect since this property implies the resolution of some packing problems in polynomial time. Given a 0-1 matrix M, Q(M) denotes the graph whose cliques have their incidence vectors as the rows of M. A 0-1 matrix M is perfect if it is the clique-node matrix of Q(M) and Q(M) is a perfect graph. First, we define a set T of seven graphs and prove that N[G] is a clique-node matrix if and only if every node induced subgraph of G in the set T, has a common neighbour in G. Second, we define two families of graphs, called H-graphs and A-graphs, and prove that Q(N[G]) does not have an induced odd hole if and only if G has no H-subgraph for some additional conditions on G. Finally, we show that Q(N[G]) does not have an induced odd antihole if and only if G has neither an A-subgraph nor a web graph Wt4t+3 in suitable sets of nodes of V(G), thus completing a characterization of graphs with perfect closed neighbourhood matrix.
Mariana S. Escalante, Erica G. Hinrichsen
LAGOS2
2020 Labelled packing functions in graphs
Erica G. Hinrichsen, Valeria A. Leoni, Martín Darío Safe
Inf. Process. Lett.1
2015 Generalized limited packings of some graphs with a limited number of P4-partners
Maria Patricia Dobson, Erica G. Hinrichsen, Valeria A. Leoni
Theor. Comput. Sci.2
2014 k -Packing Functions of Graphs
Valeria A. Leoni, Erica G. Hinrichsen
ISCO2