LJLijo M. Jose

Lijo M. Jose

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Lijo M. Jose has a total of 5 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Face-Hitting Dominating Sets in Planar Graphs

    by P. Francis, Abraham M. Illickan, Lijo M. Jose, Deepak Rajendraprasad


  • Open Access

    Maximal Independent Sets in Planar Triangulations

    by P. Francis, Abraham M. Illickan, Lijo M. Jose, Deepak Rajendraprasad

    We show that every planar triangulation on $n$ vertices has a maximal independent set of size at most $n/3$. This affirms a conjecture by Botler, Fernandes and Gutiérrez [Electron.\ J.\ Comb., 2024], which in turn would follow if an open question of Goddard and Henning [Appl.\ Math.\ Comput., 2020] which asks if every planar triangulation has three disjoint maximal independent sets were answered in the affirmative. Since a maximal independent set is a special type of dominating set (independent dominating set), this is a structural strengthening of a major result by Matheson and Tarjan [Eur.\ J.\ Comb., 1996] that every triangulated disc has a dominating set of size at most $n/3$, but restricted to triangulations.

  • Open Access

    Face-hitting Dominating Sets in Planar Graphs

    by P. Francis, Abraham M. Illickan, Lijo M. Jose, Deepak Rajendraprasad

    A dominating set of a graph $G$ is a subset $S$ of its vertices such that each vertex of $G$ not in $S$ has a neighbor in $S$. A face-hitting set of a plane graph $G$ is a set $T$ of vertices in $G$ such that every face of $G$ contains at least one vertex of $T$. We show that the vertex-set of every plane (multi-)graph without isolated vertices, self-loops or $2$-faces can be partitioned into two disjoint sets so that both the sets are dominating and face-hitting. We also show that all the three assumptions above are necessary for the conclusion. As a corollary, we show that every $n$-vertex simple plane triangulation has a dominating set of size at most $(1 - α)n/2$, where $αn$ is the maximum size of an independent set in the triangulation. Matheson and Tarjan [European J. Combin., 1996] conjectured that every plane triangulation with a sufficiently large number of vertices $n$ has a dominating set of size at most $n / 4$. Currently, the best known general bound for this is by Christiansen, Rotenberg and Rutschmann [SODA, 2024] who showed that every plane triangulation on $n > 10$ vertices has a dominating set of size at most $2n/7$. Our corollary improves their bound for $n$-vertex plane triangulations which contain a maximal independent set of size either less than $2n/7$ or more than $3n/7$.

  • Disjoint total dominating sets in near‐triangulations

    by P. Francis, Abraham M. Illickan, Lijo M. Jose, Deepak Rajendraprasad

    We show that every simple planar near‐triangulation with minimum degree at least three contains two disjoint total dominating sets. The class includes all simple planar triangulations other than the triangle. This affirms a conjecture of Goddard and Henning.