On the General Position Number of Complementary Prisms

DOI10.3233/FI-2021-2006zbMATH Open1485.05038arXiv2001.02189OpenAlexW3123888514MaRDI QIDQ4989178FDOQ4989178

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)

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.

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

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

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)

Cites Work

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

Cited In (13)

• 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
• On monophonic position sets in graphs

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)