首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Graph Realizations: Maximum Degree in Vertex Neighborhoods
  • 本地全文:下载
  • 作者:Amotz Bar-Noy ; Keerti Choudhary ; David Peleg
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:162
  • 页码:10:1-10:17
  • DOI:10.4230/LIPIcs.SWAT.2020.10
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:The classical problem of degree sequence realizability asks whether or not a given sequence of n positive integers is equal to the degree sequence of some n-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles. In this paper, we initiate the study of neighborhood degree profiles, wherein, our focus is on the natural problem of realizing maximum neighborhood degrees. More specifically, we ask the following question: "Given a sequence D of n non-negative integers 0≤ dâ,â‰¤ â<¯ ≤ d_n, does there exist a simple graph with vertices vâ,,…, v_n such that for every 1≤ i ≤ n, the maximum degree in the neighborhood of v_i is exactly d_i?" We provide in this work various results for maximum-neighborhood-degree for general n vertex graphs. Our results are first of its kind that studies extremal neighborhood degree profiles. For closed as well as open neighborhood degree profiles, we provide a complete realizability criteria. We also provide tight bounds for the number of maximum neighbouring degree profiles of length n that are realizable. Our conditions are verifiable in linear time and our realizations can be constructed in polynomial time.
  • 关键词:Graph realization; neighborhood profile; extremum-degree
国家哲学社会科学文献中心版权所有