论文部分内容阅读
一般地,确定一个无爪图G(或任意一个线图L(G))的反馈点数τ(G)和控制数Υ(G)是NP-hard的.相比之下对于线图的补图要确定它的反馈点数和控制数情况就不同了.在本文中,我们提出了对于一个独立数α(C)≥≥3的无爪图C,它的补图的控制数有Υ(G)≤ 3,并且确定一个α(C)≥≥ 3的无爪图的补图的控制数是多项式的.此外,如果图G没有孤立点和孤立边且不与星图同构,则有2≤Υ(J(C≤ ≤ 3,其中J(G)是图G的线图的补图.如果图G不与星图同构且没有孤立点,则当最大度△(G)≥ 6时有τ(J(G))= n-△(G)-1.对于△(G)≤5情况我们也做出了相应的研究.从而我们得到了确定图的线图的补图的反馈点数是多项式的.图G的Wiener指标是G中所有点对的距离之和.本文中,我们确定了 J(G)的Wiener指标,其中J(G)是连通的.