| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-04-22 10:00 外平面的グラフの (2,1)-全ラベリング数のタイトな上界 蓮沼 徹（徳島大）・○石井利昌（小樽商科大）・小野廣隆（九大）・宇野裕之（阪府大）  COMP2010-1 |
|
| 抄録 | （和） | グラフ $G$ の $(2,1)$-全ラベリングとは，$G$ の節点と辺への $0$から$k$までの整数値の 割り当てであり，節点とそれに接続する辺の間では少なくとも 2，隣り合う 2 節点間または 2 辺間では 少なくとも 1 の差があるもののことをいう． $G$ の $(2,1)$-全ラベリング数 $\lambda^T_2(G)$ は， $k$ がとりうる値の最小値 として定義される． [D.~Chen and W.~Wang. (2,1)-Total labelling of outerplanar graphs. Discr. Appl. Math. {\rm 155} (2007)] では， すべての外平面的グラフ $G$ において $\lambda^T_2(G) \leq \Delta(G)+2$ が成り立つと予想され (ただし，$\Delta(G)$ は $G$ の最大次数を表す)， $\Delta(G)\geq 5$ の場合この予想は成立することも 証明されている． 本研究では， $\Delta(G)\leq 4$ の場合においても この予想が成立することを示す． |
| （英） | A $(2,1)$-total labeling of a graph $G$ is an assignment $f$ from the vertex set $V(G)$ and the edge set $E(G)$ to the set $\{0,1,\ldots,k\}$ of nonnegative integers such that $|f(x)-f(y)|\ge 2$ if $x$ is a vertex and $y$ is an edge incident to $x$, and $|f(x)-f(y)|\ge 1$ if $x$ and $y$ are a pair of adjacent vertices or a pair of adjacent edges, for all $x$ and $y$ in $V(G)\cup E(G)$. The $(2,1)$-total labeling number $\lambda^T_2(G)$ of $G$ is defined as the minimum $k$ among all possible assignments. In [D.~Chen and W.~Wang. (2,1)-Total labelling of outerplanar graphs. Discr. Appl. Math. {\rm 155} (2007)], it was conjectured that all outerplanar graphs $G$ satisfy $\lambda^T_2(G) \leq \Delta(G)+2$, where $\Delta(G)$ is the maximum degree of $G$, while they also showed that it is true for $G$ with $\Delta(G)\geq 5$. In this paper, we solve their conjecture completely, by proving that $\lambda^T_2(G) \leq \Delta(G)+2$ even in the case of $\Delta(G)\leq 4 $. |
|
| キーワード | （和） | (2,1)-全ラベリング / 外平面的グラフ / 最大次数 / 距離制約付きラベリング / / / / |
| （英） | (2,1)-total labeling / Outerplanar graph / Maximum degree / Distance constrained labeling / / / / | |
| 文献情報 | 信学技報, vol. 110, no. 12, COMP2010-1, pp. 1-8, 2010年4月. | |
| 資料番号 | COMP2010-1 | |
| 発行日 | 2010-04-15 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2010-1 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2010-04-22 - 2010-04-22 |
| 開催地（和） | 立命館大学 びわこ・くさつキャンパス |
| 開催地（英） | Ritusmeikan University, Biwako-Kusatsu Campus |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2010-04-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 外平面的グラフの (2,1)-全ラベリング数のタイトな上界 |
| サブタイトル（和） | |
| タイトル（英） | A tight upper bound on the (2,1)-total labeling number of outerplanar graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | (2,1)-全ラベリング / (2,1)-total labeling |
| キーワード(2)（和/英） | 外平面的グラフ / Outerplanar graph |
| キーワード(3)（和/英） | 最大次数 / Maximum degree |
| キーワード(4)（和/英） | 距離制約付きラベリング / Distance constrained labeling |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 蓮沼 徹 / Toru Hasunuma / ハスヌマ トオル |
| 第1著者 所属（和/英） | 徳島大学 (略称： 徳島大) The University of Tokushima (略称： Univ. Tokushima) |
| 第2著者 氏名（和/英/ヨミ） | 石井 利昌 / Toshimasa Ishii / イシイ トシマサ |
| 第2著者 所属（和/英） | 小樽商科大学 (略称： 小樽商科大) Otaru University of Commerce (略称： Otaru Univ. Commerce) |
| 第3著者 氏名（和/英/ヨミ） | 小野 廣隆 / Hirotaka Ono / オノ ヒロタカ |
| 第3著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 宇野 裕之 / Yushi Uno / ウノ ユウシ |
| 第4著者 所属（和/英） | 大阪府立大学 (略称： 阪府大) Osaka Prefecture University (略称： Osaka Pref. Univ.) |
| 講演者 | 第2著者 |
| 発表日時 | 2010-04-22 10:00:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2010-1 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.12 |
| ページ範囲 | pp.1-8 |
| ページ数 | 8 |
| 発行日 | 2010-04-15 (COMP) |
[研究会発表申込システムのトップページに戻る]