<p>Méziane Aïder (2002) introduced the concept of almost distance-hereditary (dh) graphs by relaxing distance constraints. In these graphs, the distance between any two vertices in an induced subgraph can be either equal or one greater than their distance in the original graph. Aïder further suggested that this condition on distances can be generalized by allowing the distance between two vertices in an induced subgraph to be at most <i>r</i> more than their distance in the original graph. The class of such graphs is denoted by <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathscr {D}(r)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">D</mi> <mo stretchy="false">(</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. He raised an open problem, namely the question of the characterization of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathscr {D}(r)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">D</mi> <mo stretchy="false">(</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$r \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. In this work, specific attention is paid to the case when <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$r=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and such graphs are named as almost-2-dh. A complete classification for almost-2-dh graphs involving their forbidden subgraphs is provided, thereby resolving Aïder’s problem with <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$r=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

A characterization of almost-2-distance-hereditary graphs in terms of their forbidden subgraphs

期刊论文
发表日期：

2026年6月1日

查看全文

S. Hayat,
R. Sundareswaran,
M. Shanmugapriya,
P. Amalorpavamary,
A. Khan,
T. Saidani,
V. Swaminathan

摘要

Méziane Aïder (2002) introduced the concept of almost distance-hereditary (dh) graphs by relaxing distance constraints. In these graphs, the distance between any two vertices in an induced subgraph can be either equal or one greater than their distance in the original graph. Aïder further suggested that this condition on distances can be generalized by allowing the distance between two vertices in an induced subgraph to be at most r more than their distance in the original graph. The class of such graphs is denoted by $\mathscr {D}(r)$ $D (r)$ . He raised an open problem, namely the question of the characterization of $\mathscr {D}(r)$ $D (r)$ , $r \ge 2$ $r \geq 2$ . In this work, specific attention is paid to the case when $r=2$ $r = 2$ and such graphs are named as almost-2-dh. A complete classification for almost-2-dh graphs involving their forbidden subgraphs is provided, thereby resolving Aïder’s problem with $r=2$ $r = 2$ .