18 papers · 1 filter
Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms
Julian D. Allagan, Kevin Pereyra, William A. Massey
On a network with a fixed set of verified sources, discounted averaging induces an equilibrium support , the discounted probability that a random walk…
Generalized Sterboul--Deming Configurations
Daniel A Jaume, Cristian Panelo, Kevin Pereyra
Sterboul and Deming gave classical matching-based characterizations of non-Kőnig--Egerváry graphs through flower--posy and blossom-pair configurations. We consider two classical co…
On the Extremal Energy of Complex Unit Gain Dumbbell Graphs
Silin Huang, Kevin Pereyra
We study the extremal energy problem for complex unit gain graphs whose underlying graph is the dumbbell graph . Using switching equivalence, we reduce the spectrum t…
A Ridge-Saturation Characterization of -Critical Graphs
Do Trong Hoang, Vadim E. Levit, Eugen Mandrescu +1
We characterize the graphs which are simultaneously -critical and members of the class . The characterization is stated in three equivalent languages. In the graph…
The 2-Quasi-Regularizability Conjecture and Independence Polynomials of Wp Graphs
Kevin Pereyra
Hoang, Levit, Mandrescu and Pham asked for structural conditions ensuring that the independence polynomial of a $\W_p$ graph is log-concave, or at least unimodal, and conjectured t…
On the Determinant of Kőnig-Egerváry Graphs
Kevin Pereyra
Several graph decompositions that factorize the determinant of the adjacency matrix isolate a Kőnig-Egerváry part, such as the SD--KE decomposition and the critical independence de…
Graphs with core(G) = nucleus(G)
Vadim E. Levit, Eugen Mandrescu, Kevin Pereyra
Let be a finite simple graph. An independent set of is critical if for every independent set o…
Structural and Polynomial-Time Results on Core and Corona in Odd-Bicyclic Graphs
Kevin Pereyra
Let $\core G$ and $\corona G$ denote the intersection and the union, respectively, of all maximum independent sets of a graph . In this work, we show that for a graph with at mo…
Core and Corona in 2-Bicritical Odd-Bicyclic Graphs
Kevin Pereyra
Let $\core G$ and $\corona G$ denote the intersection and the union, respectively, of all maximum independent sets of a graph . A graph is called \emph{-bicritical} if $\a{N(…
A characterization of graphs with $\a{\corona G}+\a{\core G}=2α(G)+1$
Kevin Pereyra
A Kőnig--Egerváry graph is a graph satisfying , where , , and denote the independence number, the matching number, and the order of , resp…
On the minimum degree of minimal --factor critical -planar graphs
Kevin Pereyra
A graph of order is said to be -\emph{factor-critical} if the removal of any vertices results in a graph with a perfect matching. A -factor-critical grap…
Inequalities Involving Core, Corona, and Critical Sets in General Graphs
Adrián Pastine, Kevin Pereyra
Let denote the cardinality of a maximum independent set. An independent set of is critical if f…
On Bipartite-Almost Bipartite Graphs and the Determinantal Factorization
Kevin Pereyra
A graph is almost bipartite if it contains exactly one odd cycle, and it is Konig-Egervary if the sum of the independence number and the matching number equals the order of the gra…
On R-disjoint graphs: a generalization of almost bipartite non-König-Egerváry graphs
Kevin Pereyra
An almost bipartite graph is a graph with a unique odd cycle. Levit and Mandrescu showed that in every non-König--Egerváry almost bipartite graph the equalities $\textnormal{ker}(G…
Sterboul-Deming Graphs: Characterizations
Kevin Pereyra
A graph is said to be a Sterboul--Deming graph if , that is, if every vertex of belongs to a posy or a flower (structures introduced by Sterboul, Deming, and E…
Generalized Edmonds-Sterboul-Deming configurations. Part 1: Sterboul-Deming graphs
Daniel A. Jaume, Cristian Panelo, Kevin Pereyra
We introduce two new types of graph configurations, the Jflower and the Jposy, which generalize the classical flower and posy configurations of Edmonds, Sterboul, and Deming in the…
Generalized Edmonds-Sterboul-Deming configurations Part 3: Determinantal multiplicativity of the SD-KE decomposition of matchable graphs
Daniel A. Jaume, Diego G. Martinez, Cristian Panelo +1
In this work it is shown that the SD-KE decomposition is multiplicative under determinantal-type functions for graphs with perfect matchings, providing a new tool for the study of…
On the nullspace of split graphs
Daniel A. Jaume, Victor N. Schvöllner, Cristian Panelo +1
We study the nullspace of the adjacency matrix of split graphs, whose vertex set can be partitioned into a clique and an independent set. We introduce the clique-kernel, a subspace…