A Steiner general position problem in graph theory

DOI10.1007/S40314-021-01619-YzbMATH1476.05043OpenAlexW3195797667MaRDI QIDQ2245772FDOQ2245772

Authors Sandi Klavžar, Dorota Kuziak, Iztok Peterin, Ismael G. Yero

Publication date 15 November 2021

Published in Computational and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Steiner distancejoin of graphslexicographic product of graphsSteiner general position numberSteiner general position set

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Let $G$ be a graph. The Steiner distance of $WsubseteqV(G)$ is the minimum size of a connected subgraph of $G$ containing $W$. Such a subgraph is necessarily a tree called a Steiner $W$-tree. The set $AsubseteqV(G)$ is a $k$-Steiner general position set if $V(T_B)capA=B$ holds for every set $BsubseteqA$ of cardinality $k$, and for every Steiner $B$-tree $T_B$. The $k$-Steiner general position number ${msgp}_k(G)$ of $G$ is the cardinality of a largest $k$-Steiner general position set in $G$. Steiner cliques are introduced and used to bound ${msgp}_k(G)$ from below. The $k$-Steiner general position number is determined for trees, cycles and joins of graphs. Lower bounds are presented for split graphs, infinite grids and lexicographic products. The lower bound for the latter products leads to an exact formula for the general position number of an arbitrary lexicographic product.

Recommendations

• Some Steiner concepts on lexicographic products of graphs
• Steiner Numbers in Graphs
• The general position problem on Kneser graphs and on some graph operations
• Steiner distance in product networks
• scientific article; zbMATH DE number 1439409

Cites work

• A general position problem in graph theory
• Bounding the \(k\)-Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence
• Characterization of classes of graphs with large general position number
• Characterization of general position sets and its applications to cographs and bipartite graphs
• Convex sets in lexicographic products of graphs
• General \(d\)-position sets
• Graphs with 4-Steiner convex balls
• On general position sets in Cartesian products
• On the General Position Number of Complementary Prisms
• On the extremal combinatorics of the Hamming space
• On the general position problem on Kneser graphs
• On the inverse Steiner Wiener problem
• Steiner convex sets and Cartesian product
• Steiner distance and convexity in graphs
• Steiner distance in graphs
• Steiner distance in product networks
• Steiner trees and convex geometries
• The Steiner Wiener index of a graph
• The general position number of Cartesian products involving a factor with small diameter
• The general position number of integer lattices
• The general position number of the Cartesian product of two trees
• 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
• \(n\)-ary transit functions in graphs

Cited in

(12)

• The general position avoidance game and hardness of general position games
• Steenrod problem and the domination relation
• The general position achievement game played on graphs
• The average Steiner \(( 3 , 2 )\)-eccentricity of trees
• On the general position numbers of maximal outerplane graphs
• Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products
• On the general position number of Mycielskian graphs
• On monophonic position sets in graphs
• On the general position number of the k -th power graphs
• The general Steiner problem in Boolean space and application
• Some Steiner concepts on lexicographic products of graphs
• scientific article; zbMATH DE number 1532673 (Why is no real title available?)

This page was built for publication: A Steiner general position problem in graph theory

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