← 研踪 PaperTrailarXiv:2611.06636 · v1
Non-induced inherent graphs
首次提交 2026-11-04 23:18
版本更新 2026-11-04 23:18
雷达观测 2026-11-05 12:13
摘要
Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete characterizations of inherent two-rooted paths and forks. We show that for these families, the obvious necessary condition for inherence from the induced case is sufficient in the NNI setting. To complement these results, we introduce two general methods for proving non-inherence and apply them to demonstrate the non-inherence of several classes of two-rooted trees. Keywords: subgraph, two-rooted graph, two-rooted tree, avoidable two-rooted graph, inherent two-rooted graph
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-04 23:18 · 最新观测版本
Non-induced inherent graphs
Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete characterizations of inherent two-rooted paths and forks. We show that for these families, the obvious necessary condition for inherence from the induced case is sufficient in the NNI setting. To complement these results, we introduce two general methods for proving non-inherence and apply them to demonstrate the non-inherence of several classes of two-rooted trees. Keywords: subgraph, two-rooted graph, two-rooted tree, avoidable two-rooted graph, inherent two-rooted graph
查看此版本解读 →查看此版本原文 ↗