On the General Position Number of Complementary Prisms

DOI10.3233/FI-2021-2006MaRDI QIDQ4989178zbMATH OpenOpenAlexFDO

Authors S. V. Ullas Chandran, Manoj Changat, Sandi Klavžar, P. K. Neethu

Publication date 21 May 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.02189

zbMATH Keywords

bipartite graphsplit graphblock graphcomplementary prismgeneral position set

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Other designs, configurations (05B30) Distance in graphs (05C12) Graph designs and isomorphic decomposition (05C51)

Abstract: The general position number $mgp(G)$ of a graph $G$ is the cardinality of a largest set of vertices $S$ such that no element of $S$ lies on a geodesic between two other elements of $S$. The complementary prism $GoverlineG$ of $G$ is the graph formed from the disjoint union of $G$ and its complement $overlineG$ by adding the edges of a perfect matching between them. It is proved that $mgp(GoverlineG)len(G)+1$ if $G$ is connected and $mgp(GoverlineG)len(G)$ if $G$ is disconnected. Graphs $G$ for which $mgp(GoverlineG)=n(G)+1$ holds, provided that both $G$ and $overlineG$ are connected, are characterized. A sharp lower bound on $mgp(GoverlineG)$ is proved. If $G$ is a connected bipartite graph or a split graph then $mgp(GoverlineG)inn(G),n(G)+1$. Connected bipartite graphs and block graphs for which $mgp(GoverlineG)=n(G)+1$ holds are characterized. A family of block graphs is constructed in which the $mgp$-number of their complementary prisms is arbitrary smaller than their order.

Recommendations

• On the geodetic number of complementary prisms
• A note on the convexity number for complementary prisms
• Domination and total domination in complementary prisms
• Complexity properties of complementary prisms
• The geodetic hop domination number of complementary prisms
• A note on the convexity number of the complementary prisms of trees
• \(k\)-tuple total domination in complementary prisms
• Locating-domination in complementary prisms
• Supereulerian graphs in generalized prisms and complementary prisms
• On the domination number of prisms of graphs

Cites work

• A general position problem in graph theory
• A note on the convexity number for complementary prisms
• A note on the no-three-in-line problem on a torus
• Characterization of general position sets and its applications to cographs and bipartite graphs
• Complexity properties of complementary prisms
• Cycles in complementary prisms
• Domination and total domination in complementary prisms
• Finding points in general position
• No-three-in-line problem on a torus: periodicity
• On no-three-in-line problem on \(m\)-dimensional torus
• On the General Position Subset Selection Problem
• On the general position problem on Kneser graphs
• Spectra, signless Laplacian and Laplacian spectra of complementary prisms of graphs
• The complementary product of two graphs
• The general position number of integer lattices
• The general position problem and strong resolving graphs
• The general position problem on Kneser graphs and on some graph operations
• The graph theory general position problem on some interconnection networks

Cited in

(13)

• On monophonic position sets in graphs
• On the monophonic convexity in complementary prisms
• A Steiner general position problem in graph theory
• Geometric and topological properties of the complementary prism networks
• On general position sets in Cartesian products
• Characterization of general position sets and its applications to cographs and bipartite graphs
• The core of a complementary prism
• The core of a vertex-transitive complementary prism
• On the general position numbers of maximal outerplane graphs
• On the general position number of the k -th power graphs
• On independent position sets in graphs
• General \(d\)-position sets
• The edge general position problem

This page was built for publication: On the General Position Number of Complementary Prisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989178)