ブロックグラフにおける三つの支配に基づく識別問題

入力グラフの最小サイズの識別、定位支配、およびオープン定位支配コードを決定する問題は、理論的および計算的視点から挑戦的な特別な探索問題です。これらの問題では、グラフGの支配集合Cを選択し、選ばれたV(G)の部分集合の頂点（つまり、V(G) \ CまたはV(G)自体）がC内の隣接点によって一意に決定されるようにします。これらの問題に対する典型的なアプローチは、さまざまなグラフクラスにおける最小コードの厳密な境界を決定することです。本研究では、ブロックグラフ（すなわち、ダイヤモンドを含まないコードグラフ）に対するすべての3種類のコードに対して厳密な下限および上限を示します。我々の境界は、ブロックグラフの最大クリーク（またはブロック）の数およびグラフの順序に関するものです。我々の上限のうち2つは、文献からの予想を検証し、そのうちの1つはこの論文でブロックグラフに対して証明されました。下限については、ブロックの数とブロックグラフの順序の両方に関して線形であることを証明します。これらの境界を達成するブロックグラフのファミリーの例を示し、したがって各境界が厳密であることを示します。