.png){kind=icon}
返回
Degree Realization by Bipartite Multigraphs∗
.png){kind=icon}
PRE
AI
DOI：10.46298/dmtcs.15158.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
给定度序列的多重图实现问题可视为经典度实现问题（其中实现图为简单图）的松弛。本文关注实现多重图要求为二分图的情况。刻画可由二分（简单）图实现的度序列问题有两种变体。在较简单的变体中，称为BDRP，将度序列划分为两边的划分作为输入的一部分给出。Gale和Ryser六十多年前给出了该变体可实现的完全刻画。然而，划分未给出的变体，称为BDR，仍为开放问题。对于二分多重图实现，也有两种变体。对于BDRP，划分作为输入的一部分给出，已知存在完全刻画以确定是否存在其底图为二分图的多重图实现，且边的最大复制数不超过r。我们给出完全刻画以确定是否存在二分多重图实现，且总冗余边数不超过t。我们证明优化这两个度量可能导致不同的实现，且按一个度量优化可能显著增加另一个度量。至于BDR变体，划分未给出，我们证明确定给定（单个）序列是否接受二分多重图实现是NP难的。此外，我们证明该难度结果可扩展至任何二分图子族且路径图超族的图族。在正面方面，我们提供一种算法，计算平衡划分数量为多项式时的最优实现，并给出仅依赖于序列最大度的二分多重图实现存在性的充分条件。
Keyword:
Degree Sequences
Graph Realization
Bipartite Graphs
Graphic Sequences
Bigraphic Sequences
Multigraph Realization
期刊
D
IF:
0.5
论文数:
3
被引数:
485
机构
查看更多机构
引用论文
暂无论文信息