A Steiner general position problem in graph theory

2021/05/18 by Klavžar, Sandi, Kuziak, Dorota, Peterin, Iztok +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2105.08391

Abstract

Let G be a graph. The Steiner distance of W⊆ V(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 A⊆ V(G) is a k-Steiner general position set if V(T_B)∩ A = B holds for every set B⊆ A of cardinality k, and for every Steiner B-tree T_B. The k-Steiner general position number \rm sgp_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 \rm sgp_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.

Cited by

• Varieties of mutual-visibility and general position on Sierpiński graphs

Related

• Steiner Distance in Graphs--A Survey
• The general position problem on Kneser graphs and on some graph\n operations
• Solving group Steiner problems as Steiner problems: the rigorous proof
• Linear algorithms on Steiner domination of trees
• Steiner (revised) Szeged index of graphs