Original title: Monophonic position sets of Cartesian and lexicographic products of graphs
Ullas Chandran S V, Sandi Klavžar, P K Neethu, James Tuite · September 2026
In network math, a graph is a collection of points joined by lines. Researchers study special point groups where no induced path—a single, simple line of connections with no shortcuts—passes through more than two chosen points. Finding the largest group of this kind is called the monophonic position problem. Here, researchers explored what happens when you combine simpler graphs into bigger ones using Cartesian and lexicographic products. For Cartesian combinations, they proved these groups can only take one of three basic setups: layered, varied, or cliquey. They also set lower and upper limits for the largest group size, which match completely when neither starting graph has simple, clustered points called simplicial vertices. Finally, they built an exact formula for lexicographic combinations.
Imagine selecting a group of people for a committee so that no two members who are not directly connected by friendship are linked through a chain of friendships that excludes all other non-members. Now combine two different social networks by linking people in a grid. In this paper, the possible committee selections in combined networks only take three forms, such as picking from one network at a time or from a clique.
Understanding monophonic position sets helps compute maximum vertex sets with no induced path containing more than two. In product graphs, which model networks, this paper gives exact structure and formulas. This simplifies computing such sets and advances graph theory.
The bounds for Cartesian products are not always tight; they coincide only when neither factor has simplicial vertices. The formula for lexicographic products depends on the monophonic sets of the second factor, which may be complex to compute. The paper does not address other graph products or the general position problem variant.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
Monophonic position sets of Cartesian and lexicographic products of graphs — Ullas Chandran S V, Sandi Klavžar, P K Neethu et al. — Computational & applied mathematics — doi:10.1007/s40314-026-03901-3
Abstract licence: CC BY
Explanation generated by Synthesis from the abstract — it is not the original paper.