文章导读
总览 评价 刘清海 1，* ， 洪艳梅 2， （ 1、 福州大学离散数学研究中心,福州 350108 ； 2、 福州大学数学与计算机科学学院,福州 350108； ） 摘要： 设~$D$ 为点集为~${v_1,ldots, v_n}$ 的有向图,则序列~${(d^+(v_1),d^-(v_1)),ldots, (d^+(v_n)$, $d^-(v_
刘清海1，*， 洪艳梅2，
（
1、福州大学离散数学研究中心,福州 350108 ； 2、福州大学数学与计算机科学学院,福州 350108； ）
摘要：
设~$D$ 为点集为~${v_1,ldots, v_n}$ 的有向图,则序列~${(d^+(v_1),d^-(v_1)),ldots, (d^+(v_n)$, $d^-(v_n))}$ 称为~$D$ 的度序列。对任意给定一个整数对构成的序列~$mathbf{d}={(d_1^+, d_1^-), ldots, (d_n^+, d_n^-)}$,以及整数~$k$, 如果存在~$k$ 强连通有向图~$D$ 以~$mathbf d$ 为度序列,则称~$mathbf{d}$ 为~$k$-强连通可实现度序列并且称~$D$ 为序列~$mathbf d$ 的一个~$k$-强连通实现。 本文主要给出一个序列~$mathbf{d}$ 是~$k$-强连通可实现序列的刻画,并且可以在线性时间内验证。
关键词：
有向图；度序列；度实现；$k$-弧强连通
Qinghai Liu1,*， Yanmei Hong2,
（
1、Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108 ； 2、College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108； ）
Abstract：
Let $D$ be a digraph on ${v_1,ldots, v_n}$. Then the sequence ${(d^+(v_1), d^-(v_1)), ldots,(d^+(v_n), d^-(v_n))}$ is called the degree sequence of $D$. For any given a sequence of pairs of integers $mathbf{d}={(d_1^+, d_1^-), ldots, (d_n^+, d_n^-)}$, if there exists a $k$-arc strong connected digraph $D$ such that$mathbf d$ is the degree sequence of $D$ then $mathbf d$ is realizable and $D$ is a realization of $mathbf d$. In this paper, a characterization for a $k$-arc connected realizable sequence is given and it can be checked in a linear time.
Tag：
点此返回栏目查看更多>>>参考论文
