Korean J. Math. Vol. 23 No. 1 (2015) pp.29-36
DOI: https://doi.org/10.11568/kjm.2015.23.1.29

Base of the non-powerful signed tournament

Article Sidebar

PDF
Published: Mar 30, 2015
Keywords:
base, signed digraph, sign pattern matrix, tournament.
Mathematics Subject Classification:
05C20, 15B35.

Main Article Content

Byeong Moon Kim
Department of Mathematics Gangneung-Wonju National University Gangneung 210-702, Korea
Byung Chul Song
Department of Mathematics Gangneung-Wonju National University Gangneung 210-702, Korea

Abstract

A signed digraph $S$ is the digraph $D$ by assigning signs $1$ or $-1$ to each arc of $D$. The base of $S$ is the minimum number $k$ such that there is a pair walks which have the same initial and terminal point with length $k$, but different signs. In this paper we show that for $n\geq 5$ the upper bound of the base of a primitive non-powerful signed tournament $S_n$, which is the signed digraph by assigning $1$ or $-1$ to each arc of a primitive tournament $T_n$, is ${\rm max}\{2n+2, n+11\}$. Moreover we show that it is extremal except when $n=5,7$.


Article Details

Supporting Agencies

This work was supported by the Research Institute of Natural Science of Gangneung-Wonju National University.

References

[1] V. K. Balakrishnan, Graph theory, McGraw-Hill,N.Y., 1997. Google Scholar

[2] Y. Gao, Y. Huang and Y. Shao, Bases of primitive non-powerful signed symmetric digraphs with loops, Ars. Combinatoria 90 (2009), 383–388. Google Scholar

[3] B. Li, F. Hall and J. Stuart, Irreducible powerful ray pattern matrices, Linear Algebra and Its Appl., 342 (2002), 47–58. Google Scholar

[4] Q. Li and B. Liu, Bounds on the kth multi-g base index of nearly reducible sign pattern matrices, Discrete Math. 308 (2008), 4846–4860. Google Scholar

[5] J. Moon and N, Pullman, On the powers of tournament matrices, J. Comb. Theory 3 (1967), 1–9. Google Scholar

[6] Y. Shao and Y. Gao, The local bases of non-powerful signed symmetric digraphs with loops, Ars. Combinatoria 90 (2009), 357–369. Google Scholar

[7] B. Song and B. Kim, The bases of primitive non-powerful complete signed graphs, Korean J. Math. 22 (2014), 491–500. Google Scholar

[8] L. You, J. Shao and H. Shan, Bounds on the bases of irreducible generalized sign pattern matrices, Linear Algebra and Its Appl. 427 (2007), 285–300. Google Scholar