Digraphs that have at most one walk of a given length with the same endpoints

被引：15

作者：

Huang, Zejun ^{[1
]}

Zhan, Xingzhi ^{[1
]}

机构：

[1] E China Normal Univ, Dept Math, Shanghai 200241, Peoples R China

来源：

DISCRETE MATHEMATICS | 2011年 / 311卷 / 01期

关键词：

Digraph; Walk; Number of arcs; Tournament;

D O I：

10.1016/j.disc.2010.09.025

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let Theta(n, k) be the set of digraphs of order n that have at most one walk of length k with the same endpoints. Let theta(n, k) be the maximum number of arcs of a digraph in Theta(n, k). We prove that if n >= 5 and k >= n - 1 then theta(n, k) = n(n - 1)/2 and this maximum number is attained at D if and only if D is a transitive tournament. theta(n, n - 2) and theta(n, n - 3) are also determined. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：70 / 79

页数：10