对称本原有向图的重上广义本原指数

一个有向图Ｄ称为本原有向图，若存在某自然数Ｋ，使Ｄ中任一点ｕ到任一点ｕ都有长为ｋ之途径。本文中，我们决定具有最小奇圈长ｒ的ｎ阶对称本原有向图的第ｋ第上广义本原指数的最大数。     

对称本原有向图广义重上指数的极图刻划

一个有向图Ｄ称为本原有向图,若存在某自然数ｋ,使Ｄ中任一点ｕ到任 一点ｖ都有长为ｋ之途径．若Ｄ是一个对称有向图,则Ｄ是本原的当且仅当Ｄ对 应的无向图连通且至少包含一个奇圈。文［２］给出了具有最小奇圈长ｒ的ｎ阶对称本 原有向图广义ｋ重上指数的最大数．本文将在此基础上,给出其极图的完全刻划．     

对称本原图的集指数与本原简单图的广义上指数的极图

一个有向图D称为本原的，如果存在某个正整数k，使得对于D中的任一点x到任一点y都有长为k的途径，这样的正整数k中的最小者称为D的本原指数，作为本原指数概念的推广，R．A．Brualdi和柳柏濂于1990年引入了本原有向图的广义本原指数的新概念，本文给出了对称本原图的集指数的一些性质，并对本原简单图的广义上指数的极图进行了完全刻划。     

一类特殊的本原不可幂对称带号有向图的基指数的上界

一个本原不可幂带号有向图s的基指数l(s)是这样的最小正整数l,使得在s中,从任意一点u到任意一点v都有一对长为l的sssD途径.本文研究了n阶最小奇圈长为r的本原不可幂对称带号有向图的基指数,给出了这类有向图的基指数的最大值.     

一类本原图的重下指数的刻划

本研究一类本原有向图的广义重下指数集，证明了n(≥3）阶围长为2的本原有向图的广义k（≥2）重下指数的最大值为n-k，并给出其指数集的完全刻划。     

一类本原图的重下指数的刻划

本文研究一类本原有向图的广义重下指数集 ,证明了 n(≥ 3)阶围长为 2的本原有向图的广义 k(≥ 2 )重下指数的最大值为 n-k,并给出其指数集的完全刻划 .     

对称本原有向图的广义本原指数集

本文证明了全体ｎ阶对称本原有向图的第ｋ个第一类（１≤ｋ＜ｎ－１）、第二类（１≤ｋ≤ｎ－１）和第三类（２≤ｋ≤ｎ－１）广义本原指数的指数集分别是｛１，２，…，ｎ－２＋ｋ｝和｛１，２，…，２（ｎ－ｋ）｝，其中「ａ］表不小于ａ的最小整数，［ｂ］表不大于ｂ的最大整数。     

广义本原指数的缺数系

运用数论和图论技巧，得到了当λ（Ｄ）３时本原有向图Ｄ的广义指数ｅｘｐ（Ｄ，ｋ）的界，这里λ（Ｄ）表示Ｄ中不同长的圈的类数，还证明了对任何整数ｎ，ｔ，不存在ｎ阶本原有向图Ｄ，使得ｎ２－ｔｎ＋１４（ｔ＋１）２＋ｋ－２＜ｅｘｐ（Ｄ，ｋ）＜ｎ２－（ｔ－１）ｎ＋ｔ＋ｋ－３．     

本原对称有向图上广义指数的极图

设D是n阶有向图(允许有环但不允许有重复弧),X C V(D),集指数expD(X)是这样的最小正整数P,使得对D中每个点v,存在从X的至少一个点到V的长为P的途径.若这样的正整数P不存在,则定义expD(X)=∞.D的第k重上广义指数F(D,k):=max{expD(X)| X C V(D),|X|=k},1≤k≤n.如果F(D,k)<∞,则称D是k-上本原的.本文完全刻划了k-上本原对称有向图的第k重上广义指数的极图.     

广义本原指数及其极图的完全刻划

本文利用图论和数论相结合的方法，给出了广义本原指数达到最大值和次大值的极图的完全刻划，解决了文［３］中提到的ＥＭ问题，并同时证明了广义本原指数集合中缺数段的存在性。本文还给出了对称本原有向图类中广义本原指数达到最大值的极图的完全刻划。     

具有给定指数的本原有向图的Hamilton性质

本文解决了１９８２年Ｊ．Ａ．Ｒｏｓｓ提出的两个问题,并得到如下结果：（１）设Ｄ是具有围长ｓ＞１和指数γ（Ｄ）＝ｎ＋ｓ（ｎ－２）的ｎ阶本原有向图,则Ｄ是Ｈａｍｉｌｔｏｎ的;（２）设Ｄ是含有环的ｎ阶本原有向图且γ（Ｄ）＝２ｎ－２,则Ｄ是Ｈａｍｉｌｔｏｎ的当且仅当ｍａｘ｛ｄ（ｕ,ｖ）|γ（ｕ,ｖ）＝２ｎ－２｝＝ｎ－２．     

一类含有奇数个顶点的三色有向图本原指数上界

一个三色有向图D是本原的,当且仅当存在非负整数h、k和v,且h+k+v0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,v)-途径,h+k+v的最小值定义为三色有向图D的本原指数.研究了一类三色有向图,它的未着色图中包含2佗-4个顶点,一个n-圈、一个(n-2)-圈和一个2-圈,给出了本原指数上界.     

一类极小本原对称图的指数集

运用有向图方法完全确定出顶点带环的n阶极小本原对称有向图的本原指数集,所得的结论是:1)顶点全部自带环的n阶极小本原对称有向图所成的子图类之本原指数集E1={2,3,…,n-1};2)顶点不全带环的n阶极小本原对称有向图所成的子图类之本原指数集E2={2,3,…,2n-2}\S,其中S是{n,n+1,…,2n-2}中的所有奇数之集;3)顶点带环的n阶极小本原对称有向图所成的特殊图类之本原指数集En=E1∪E2={2,3,…,2n-2}\S.     

本原不可幂带号有向图的lewin数的界

如果存在正整数k使得对于D中任意两点u和v(允许u=v),在D中都有从u到v的长为k的有向途径,则称有向图D是本原的.给有向图的每条弧赋以符号+1或者-1得到的图S称为带号有向图.如果带号有向图S中包含SSSD途径对,即包含两条有相同的起点,相同的终点,相同的长度,并且有不同的符号的途径对,则称S是不可幂的.在本文中,我们将Lewin M提出的lewin数的概念从本原有向图推广到本原不可幂带号有向图,给出了本原不可幂带号有向图S的lewin数l(S)的若干上界,并提出了一个公开问题.     

一类本原无向图的广义上指数的极图

设R（n,d)表示由全体恰含d个环点的n(n≥3）阶本原无向图所构成的集合,F(n,d,k)为R(n,d)中图的第k重上广义本原指数的量大值,1≤d≤n,2≤k≤n-1。本文给出了第k重上广义本原指数达到F(n,d,k)的极图的完全刻画。