A Steiner general position problem in graph theory

DOI10.1007/S40314-021-01619-YzbMATH Open1476.05043arXiv2105.08391OpenAlexW3195797667MaRDI 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)

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.

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

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

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)

Cites Work

• Steiner distance and convexity in graphs
• The Steiner Wiener index of a graph
• Steiner distance in graphs
• Steiner trees and convex geometries
• On the extremal combinatorics of the Hamming space
• \(n\)-ary transit functions in graphs
• Convex sets in lexicographic products of graphs
• Graphs with 4-Steiner convex balls
• Steiner Distance in Product Networks
• Steiner convex sets and Cartesian product
• The Graph Theory General Position Problem on Some Interconnection Networks
• Bounding the \(k\)-Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence
• Title not available (Why is that?)
• On general position sets in Cartesian products
• The general position problem on Kneser graphs and on some graph operations
• The general position number of Cartesian products involving a factor with small diameter
• 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
• Characterization of classes of graphs with large general position number
• On the general position problem on Kneser graphs
• On the General Position Number of Complementary Prisms
• THE GENERAL POSITION NUMBER OF THE CARTESIAN PRODUCT OF TWO TREES
• General d-position sets

Cited In (11)

• The average Steiner \(( 3 , 2 )\)-eccentricity of trees
• The general position avoidance game and hardness of general position games
• The general position achievement game played on graphs
• Steenrod problem and the domination relation
• Title not available (Why is that?)
• 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 the k -th power graphs
• On the general position number of Mycielskian graphs
• The general Steiner problem in Boolean space and application
• On monophonic position sets in graphs

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)