Bulletin of the Australian Mathematical Society

INCIDENCE SEMIRINGS OF GRAPHS AND VISIBLE BASES

J. ABAWAJYa1, A. V. KELAREVa2 c1, M. MILLERa3a4 and J. RYANa2

a1 School of Information Technology, Deakin University, 221 Burwood, Melbourne, Victoria 3125, Australia email jemal.abawajy@deakin.edu.au

a2 School of Electrical Engineering and Computer Science, University of Newcastle, University Drive, Callaghan, NSW 2308, Australia email Joe.Ryan@newcastle.edu.au

a3 CARMA Priority Research Centre, School of Mathematical and Physical Sciences, University of Newcastle, University Drive, Callaghan, NSW 2308, Australia email Mirka.Miller@newcastle.edu.au

a4 Department of Mathematics, University of West Bohemia, Pilsen, Czech Republic email Mirka.Miller@newcastle.edu.au

Abstract

We consider the incidence semirings of graphs and prove that every incidence semiring has convenient visible bases for its right ideals and for its left ideals, and that these visible bases can be used to determine the weights of all right ideals that have maximum weight and all left ideals that have maximum weight.

(Received June 18 2013)

(Accepted August 02 2013)

(Online publication September 12 2013)

2010 Mathematics subject classification

  • primary 16Y60;
  • secondary 62H30

Keywords and phrases

  • incidence semirings;
  • right ideals;
  • balanced graphs

Footnotes

  The first author was supported by Discovery grant DP0880501 from the Australian Research Council. The second author was supported by ARC Discovery grant DP0449469. The third author was supported by ARC Discovery grant DP0450294.