Isometric subgraphs for Steiner distance

Link:
Autor/in:
Erscheinungsjahr:
2020
Medientyp:
Text
Schlagworte:
  • Zagreb Index
  • Unicyclic Graph
  • Vertex Degree
  • Quantitative Structure-Activity Relationship
  • Drug Discovery
  • Pharmaceutical Preparations
  • Zagreb Index
  • Unicyclic Graph
  • Vertex Degree
  • Quantitative Structure-Activity Relationship
  • Drug Discovery
  • Pharmaceutical Preparations
Beschreibung:
  • Let G be a connected graph and ℓ :𝐸(𝐺)→ℝ+ a length-function on the edges of G. The Steiner distance sdG(A) of A ⊆ V(G) within G is the minimum length of a connected subgraph of G containing A, where the length of a subgraph is the sum of the lengths of its edges. It is clear that every subgraph H ⊆ G, endowed with the induced length-function E(H), satisfies sdH(A) ≥ sdG(A) for every A ⊆ V(H). Given an integer k ≥ 2, we call H ⊆ G k-isometric in G if equality is attained for every A ⊆ V(H) with ∣A∣ ≤ k. A subgraph is fully isometric if it is k-isometric for every 𝑘∈ℕ. It is easy to construct examples of graphs H ⊆ G such that H is k-isometric, but not (k + 1)-isometric, so this defines a strict hierarchy of properties. We are interested in situations in which this hierarchy collapses in the sense that if H ⊆ G is k-isometric, then H is already fully isometric in G. Our first result of this kind asserts that if T is a tree and T ⊆ G is 2-isometric with respect to some length-function , then it is fully isometric. This fails for graphs containing a cycle. We then prove that if C is a cycle and C ⊆ G is 6-isometric, then C is fully isometric. We present an example showing that the number 6 is indeed optimal. We then develop a structural approach toward a more general theory and present several open questions concerning the big picture underlying this phenomenon.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/1d8e3a11-4914-4b4f-84cb-8f4b492eeb75