Monophonic position sets of Cartesian and lexicographic products of graphs.

Authors

Ullas Chandran S V, Sandi Klavžar, P K Neethu, James Tuite

Published in

Computational & applied mathematics. Volume 46. Issue 2. Pages 44. Epub Sep 11, 2026.

Abstract

The general position problem in graph theory asks for the number of vertices in a largest set S of vertices of a graph G such that no shortest path of G contains more than two vertices of S. The analogous monophonic position problem is obtained from the general position problem by replacing "shortest path" by "induced path." In this paper the monophonic position number is studied on Cartesian and lexicographic products of graphs. It is proved that in Cartesian products, a monophonic position set can only be in one of three canonical forms, named layered, varied, and cliquey. The monophonic position number of an arbitrary Cartesian product is bounded from below and above. The two bounds coincide if neither of the factors has simplicial vertices. A formula for the monophonic position number of a lexicographic product is given which only contains the clique number and the structure of monophonic sets of the second factor.

PMID:
42732237
Bibliographic data and abstract were imported from PubMed on 13 Sep 2026.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.