论文部分内容阅读
1973年,R.C.Entringer提出了确定唯一泛圈图的问题,即确定简单图G使得对3≤l≤v的每个l恰有一个长为l的圈.本文将Entringer这个问题推广到定向图中,研究了唯一泛圈有向图的若干问题.一个唯一泛圈有向图是一个定向图,且对3 ≤ l≤v的每个l,它恰好有一个长为l的有向圈,这里的v表示有向图的顶点数.设D是有向图,D中不在有向Hamilton圈上的弧称为D的有向桥,用B(D)或B表示D的有向桥的集合.若D是最大唯一泛圈有向图且B是独立的,则称D是包含独立桥的最大唯一泛圈有向图.用p(v)表示具有v个顶点包含独立桥的最大唯一泛圈有向图的数目.用f(v)(g(v))表示具有v个顶点的唯一泛圈有向图最大(小)可能的弧数.该文的主要结果是:(1)通过构造几类唯一泛圈有向图证明了f(v)=2v-3.(2)对p≥4,证明了p(v)≤ 2v-4.(3)同时得到了g(v)的上界和下界,即对v≥3,g(v)≥v+{log2(v-2)}和对v≥4,g(v)≤v+{v/2}+1.并且对每个3≤v≤20,确定了g(v),即若v∈{v|3≤v≤14}∪{19,20}-{9,13}时,g(v)=v+{log2(v-2)}.以及当v∈{v|15≤v≤18}∪{9,13}时,g(v)=v+{log2(v-2)}+1.