Score sets in oriented graphs
Author(s) -
S. Pirzada,
T. A. Naikoo
Publication year - 2008
Publication title -
applicable analysis and discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.69
H-Index - 26
eISSN - 2406-100X
pISSN - 1452-8630
DOI - 10.2298/aadm0801107p
Subject(s) - mathematics , combinatorics , vertex (graph theory) , graph , discrete mathematics
The score of a vertex v in an oriented graph D is , where and are the outdegree and indegree respectively of v and n is the number of vertices in D. The set of distinct scores of the vertices in an oriented graph D is called its score set. If a > 0 and d > 1 are positive integers, we show there exists an oriented graph with score set {a, ad, ad2,..., adn} except for a = 1, d = 2, n > 0, and for a = 1, d = 3, n > 0. It is also shown that there exists no oriented graph with score set {a, ad, ad2,..., adn}, n > 0 when either a = 1, d = 2, or a = 1, d = 3. Also we prove for the non-negative integers a1, a2,..., an with a1 1 i for i=1.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom