反復ラインダイグラフにおける高連結k-組双支配集合(一般,ネットワーク,通信のための信号処理及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
Gを頂点数nのd-正則ダイグラフとする.本論文では,全てのm≧2に対して,Gのm-反復ラインダイグラフL^m(G)におけるmin{k,[d/2]}-連結k-組双支配集合の最小濃度がkd^<m-1>nであることを示す,ただし1≦k<dとする.この結果から,(一般化)de Bruijnダイグラフ,Kautzダイグラフにおける(連結)k-組双支配集合に関する既知の結果が系として得られる.
- 2010-02-22
著者
関連論文
- Highly connected k-tuple twin dominating sets in iterated line digraphs (通信方式)
- Highly connected k-tuple twin dominating sets in iterated line digraphs (回路とシステム)
- 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
- RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- 木のL(2,1)-ラベリングに対するO(n^)時間アルゴリズム
- 木の(p, q)-全ラベリング問題
- 反復ラインダイグラフにおける高連結k-組双支配集合(一般,ネットワーク,通信のための信号処理及び一般)
- 反復ラインダイグラフにおける高連結κ-組双支配集合(一般,ネットワーク,通信のための信号処理及び一般)
- 反復ラインダイグラフにおける高連結κ-組双支配集合(一般,ネットワーク,通信のための信号処理及び一般)
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム