César Hernández-Cruz

activity

20122025

most citedOn the existence and number of

(k + 1)

-kings in

k

-quasi-transitive digraphs

14 citations · 19 across the 14 of their papers we have counts for

collaborators

Showing math.COShow all

14 papers · 1 filter

math.CO2025

Maya-Tupi graphs: a generalization of split graphs

Júlio Araújo, César Hernández-Cruz, Cláudia Linhares Sales

We define the family of Maya-Tupi graphs as those graphs that admit a partition $(A, B)$ of their vertex sets such that $A$ induces a complete multipartite graph where each part has…

math.CO2021★ 3 cited

Minimal obstructions to $(s, 1)$ -polarity in cographs

F. Esteban Contreras-Mendoza, César Hernández-Cruz

Let $k, l$ be nonnegative integers. A graph $G$ is $(k, l)$ -polar if its vertex set admits a partition $(A, B)$ such that $A$ induces a complete multipartite graph with at most $k$ pa…

math.CO2020

Minimum Weighted Szeged Index Trees

Pavol Hell, César Hernández-Cruz, Seyyed Aliasghar Hosseini

Weighted Szeged index is a recently introduced extension of the well-known Szeged index. In this paper, we present a new tool to analyze and characterize minimum weighted Szeged in…

math.CO2020

Orientations without forbidden patterns on three vertices

Santiago Guzmán-Pro, César Hernández-Cruz

Given a set $F$ of oriented graphs, a graph $G$ is an $F$ -graph if it admits an $F$ -free orientation. Building on previous work by Bang-Jensen and Urrutia, we propose a master algo…

math.CO2019

Strongly chordal digraphs and $Γ$ -free matrices

Pavol Hell, Cesar Hernandez-Cruz, Jing Huang +1

We define strongly chordal digraphs, which generalize strongly chordal graphs and chordal bipartite graphs, and are included in the class of chordal digraphs. They correspond to sq…

math.CO2019★ 1 cited

Vertex arboricity of cographs

Sebastián González Hermosillo de la Maza, Pavol Hell, César Hernández Cruz +2

Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we…

math.CO2017

Minimal obstructions to $2$ -polar cographs

Pavol Hell, César Hernández-Cruz, Cláudia Linhares Sales

A graph is a cograph if it is $P_{4}$ -free. A $k$ -polar partition of a graph $G$ is a partition of the set of vertices of $G$ into parts $A$ and $B$ such that the subgraph induced by…

math.CO2017

The strong convexity spectra of grids

Gabriela Araujo-Pardo, César Hernández-Cruz, Juan José Montellano-Ballesteros

Let $D$ be a connected oriented graph. A set $S \subseteq V (D)$ is convex in $D$ if, for every pair of vertices $x, y \in S$ , the vertex set of every $x y$ -geodesic, ( $x y$ shortest…

math.CO2017

Mixed Cages

G. Araujo-Pardo, C. Hernández-Cruz, J. J. Montellano-Ballesteros

We introduce the notion of a $[z, r; g]$ -mixed cage. A $[z, r; g]$ -mixed cage is a mixed graph $G$ , $z$ -regular by arcs, $r$ -regular by edges, with girth $g$ and minimum order. In…

math.CO2016

On the existence of $3$ - and $4$ -kernels in digraphs

Sebastián González Hermosillo de la Maza, César Hernández-Cruz

Let $D = (V (D), A (D))$ be a digraph. A subset $S \subseteq V (D)$ is $k$ -independent if the distance between every pair of vertices of $S$ is at least $k$ , and it is $ℓ$ -absorben…

math.CO2016

A dichotomy for the kernel by $H$ -walks problem in digraphs

Hortensia Galeana-Sánchez, César Hernández-Cruz

Let $H = (V_{H}, A_{H})$ be a digraph which may contain loops, and let $D = (V_{D}, A_{D})$ be a loopless digraph with a coloring of its arcs $c : A_{D} \to V_{H}$ . An $H$ -walk of $D$ is a walk…

math.CO2015★ 1 cited

Colourings, Homomorphisms, and Partitions of Transitive Digraphs

Tomás Feder, Pavol Hell, César Hernández-Cruz

We investigate the complexity of generalizations of colourings (acyclic colourings, $(k, ℓ)$ -colourings, homomorphisms, and matrix partitions), for the class of transitive digrap…

math.CO2013

Point determining digraphs, ${0, 1}$ -matrix partitions, and dualities in full homomorphisms

Pavol Hell, César Hernández-Cruz

We prove that every point-determining digraph $D$ contains a vertex $v$ such that $D - v$ is also point determining. We apply this result to show that for any ${0, 1}$ -matrix $M$ , w…

math.CO2012★ 14 cited

On the existence and number of $(k + 1)$ -kings in $k$ -quasi-transitive digraphs

Hortensia Galeana-Sánchez, César Hernández-Cruz, Manuel Alejandro Juárez-Camacho

Let $D = (V (D), A (D))$ be a digraph and $k \geq 2$ an integer. We say that $D$ is $k$ -quasi-transitive if for every directed path $(v_{0}, v_{1}, ..., v_{k})$ in $D$ , then $(v_0, v_k) \in A(…

Maya-Tupi graphs: a generalization of split graphs

Minimal obstructions to (s,1)-polarity in cographs

Minimum Weighted Szeged Index Trees

Orientations without forbidden patterns on three vertices

Strongly chordal digraphs and Γ-free matrices

Vertex arboricity of cographs

Minimal obstructions to 2-polar cographs

The strong convexity spectra of grids

Mixed Cages

On the existence of 3- and 4-kernels in digraphs

A dichotomy for the kernel by H-walks problem in digraphs

Colourings, Homomorphisms, and Partitions of Transitive Digraphs

Point determining digraphs, {0,1}-matrix partitions, and dualities in full homomorphisms

On the existence and number of (k+1)-kings in k-quasi-transitive digraphs

Minimal obstructions to $(s, 1)$ -polarity in cographs

Strongly chordal digraphs and $Γ$ -free matrices

Minimal obstructions to $2$ -polar cographs

On the existence of $3$ - and $4$ -kernels in digraphs

A dichotomy for the kernel by $H$ -walks problem in digraphs

Point determining digraphs, ${0, 1}$ -matrix partitions, and dualities in full homomorphisms

On the existence and number of $(k + 1)$ -kings in $k$ -quasi-transitive digraphs