木の最大平均部分木次数について【JST・京大機械翻訳】

Cambie Stijn; Wagner Stephan; Wang Hua

プレプリント

J-GLOBAL ID：202202207473715110 整理番号：21P0057722

木の最大平均部分木次数について【JST・京大機械翻訳】

On the maximum mean subtree order of trees

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2020年10月29日プレプリントサーバーでの情報更新日： 2021年06月10日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

ツリーのサブツリーは,再びツリー(すなわち接続)である,任意の誘導部分グラフである。木の平均サブツリー次数はそのサブツリーの頂点の平均数である。この不変量は,Jamisonによって1980年代に最初に分析された。木の次数を与える平均サブツリー次数の最大値が,常にいくつかのキャタピラーによって達成されるかどうかを,Jamisonによって提起した興味深い未解決の疑問は,常に,ある。この予想を完全に解決しないが,最大に達する樹木の異なる特徴を証明することにより,その好ましい証拠を見出した。例えば,最大平均サブツリー次数を持つ次数nのツリーの直径はnに非常に近いことを示した。さらに,最大平均サブツリー次数はn-2log_2n+O(1)に等しいことを示した。固定頂点を含むすべてのサブツリーの平均次数である局所平均サブツリー次数に対して,著者らはさらに正確で,その最大値は常にブルームによって達成され,それはn-log_2n+O(1)に等しいことを示した。【JST・京大機械翻訳】

, ,
, 【Automatic Indexing@JST】

グラフ理論基礎

, , ,

前のページに戻る