Extremal edge general position sets in some graphs

DOI10.1007/S00373-024-02770-ZMaRDI QIDQ6131296zbMATH OpenOpenAlexFDO

Authors Jing Tian, Sandi Klavžar, Elif Tan

Publication date 4 April 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

block graphcut-vertexdiametral pathedge general position setgeneral position set

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: A set of edges $XsubseteqE(G)$ of a graph $G$ is an edge general position set if no three edges from $X$ lie on a common shortest path. The edge general position number ${mgp}_{me}(G)$ of $G$ is the cardinality of a largest edge general position set in $G$. Graphs $G$ with ${mgp}_{me}(G)=|E(G)|-1$ and with ${mgp}_{me}(G)=3$ are respectively characterized. Sharp upper and lower bounds on ${mgp}_{me}(G)$ are proved for block graphs $G$ and exact values are determined for several specific block graphs.

Recommendations

• The edge general position problem
• Edge general position sets in Fibonacci and Lucas cubes
• On the general position numbers of maximal outerplane graphs
• Characterization of classes of graphs with large general position number

Cites work

• A general position problem in graph theory
• Edge general position sets in Fibonacci and Lucas cubes
• General position sets in two families of Cartesian product graphs
• Maximum number of subtrees in cacti and block graphs
• On general position sets in Cartesian products
• On the extremal combinatorics of the Hamming space
• On the general position number of two classes of graphs
• On the general position numbers of maximal outerplane graphs
• On the general position problem on Kneser graphs
• The edge general position problem
• The general position number of Cartesian products involving a factor with small diameter
• The semitotal domination problem in block graphs
• TRAVERSING A GRAPH IN GENERAL POSITION

Cited in

(8)

• On the general position number of Mycielskian graphs
• On the general position number of the k -th power graphs
• A note on the edge general position number of cactus graphs
• General position sets, colinear sets, and Sierpiński product graphs
• The general position number under vertex and edge removal
• The edge general position number of some graphs
• Graphs whose edge general position number is 4
• Generalization of edge general position problem

This page was built for publication: Extremal edge general position sets in some graphs

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