Linear Jaco Graphs: A Critical Review

Johan Kok

Abstract


The concept of linear Jaco graphs was introduced by Kok et al. [19,20]. Linear Jaco graphs are a family of finite directed graphs which are derived from an infinite directed graph, called the \(f(x)\)-root digraph. The incidence function is a linear function \(f(x) = mx + c\), \(x \in \mathbb{N}\), \(m,c \in \mathbb{N}_0\). Much research has been done for the case \(f(x) = x\).  Many interesting open problems remain for the case \(f(x)=x\) and certainly for the general case \(f(x) = mx + c\), \(m,c > 0\). Despite an elegant, almost simple definition of these graphs it remains hard and predictably impossible in some cases to derive closed formula for a number of well-known invariants. Interesting to note, is the ever so often appearance of Fibonacci and Lucas numbers as well as the Golden Ratio in some results. These observations suggest that a sound number theoretic approach might resolve some of the mystery surrounding Jaco graphs.

Keywords


Linear Jaco graph; Hope graph; Jaconian vertex; Jaconian set; Fisher algorithm; Bettina’s theorem.

Full Text:

PDF

References


C. Ahlbach, J. Usatine and N. Pippenger, Efficient algorithms for Zerckendorf arithmetic, Fibonacci Quarterly 51 (13) (2013), 249–255.

H. Abdo, S. Brandt and D. Dimitrov, The total irregularity of a graph, Discrete Mathematics and Theoretical Computer Science 16 (1) (2014), 201–206.

H. Abdo and D. Dimitrov, The total irregularity of a graph under graph operations, Miskolc Mathematical Notes 15 (1) (2014), 3–17.

Y. Alavi, A. Boals, G. Chartrand, P. Erdös, R. Graham and O. Oellerman, k-path irregular graphs, Congressus Numerantium 65 (1988), 201–210.

M.O. Albertson, The irregularity of a graph, Ars Combinatoria 46 (1997), 219–225.

A.R. Ashrafi, T. Došlic and A. Hamzeha, The Zagreb coindices of graph operations, Discrete Applied Mathematics 158 (2010), 1571–1578.

D. Bauer, F. Harary, J. Nieminen and C. Suffel, Domination alteration sets in graphs, Discrete Mathematics 47 (1983), 153–161.

J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan Press, London (1976).

J.E. Cohen, Interval graphs and food webs; A finding and a problem, Document 17696-PR, RAND Corporation (1968).

D. Cvetkovi´c and P. Rowlinson, On connected graphs with maximal index, Publications de I’Institut Mathematique Beograd 44 (1988), 29–34.

R.D. Dutton and R.C. Brigham, An extremal problem for edge domination insensitive graphs, Discrete Applied Mathematics 20 (2) (1988), 113–125.

G.H. Fath-Tabar, Old and new Zagreb indices of graphs, MATCH Communications in Mathematical and in Computer Chemistry 65 (2011), 79–84.

T.W. Haynes and M.A. Henning, Changing and unchanging domination: a classification, Discrete Mathematics 272 (2003), 65–79.

T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discussioness Mathematicae Graph Theory 20 (2001), 271–280.

M.A. Henning and D. Rautenbach, On the irregularity of bipartite graphs, Discrete Mathematics 307 (2007), 1467–1472.

D. Kalman and R. Mena, The fibonacci number - exposed, Mathematics Magazine 76 (3) (2003), 167–181.

J. Kok, Total Irregularity and ft-Irregularity of Jaco graphs, (J_n(1)), (n in mathbb{N}), arXiv: 1406.6168v2 [math.CO], August 2014.

J. Kok, A note on the Brush number of Jaco graphs, (J_n(1)), (n in mathbb{N}), arXiv: 1412.5733v1 [math.CO], 18 December 2014 (submitted).

J. Kok, P. Fisher, B. Wilkens, M. Mabula and V. Mukungunugwa, Characteristics of finite Jaco graphs, (J_n(1)), (n in mathbb{N}), arXiv: 1404.0484v1 [math.CO], 2 April 2014.

J. Kok, P. Fisher, B. Wilkens, M. Mabula and V. Mukungunugwa, Characteristics of Jaco graphs, (J_infty(a)), (a in mathbb{N}), arXiv: 1404.1714v1 [math.CO], 7 April 2014.

J. Kok and N.K. Sudev, A study on primitive holes of certain graphs, International Journal of Scientific and Engineering Research 6 (3) (2015), 631–635.

J. Kok, N.K. Sudev and C. Sudev, On the Pythagorean holes of certain graphs, arXiv: 1504.07714v1 [math.GM], 29 April 2015, (accepted for publication, Journal of Advanced Research in Pure

Mathematics).

J. Kok and C. Susanth, A note on f §-Zagreb indices in respect of Jaco graphs, (J_n(1)), (n in mathbb{N}) and the introduction of Khazamula irregularity, Pioneer Journal of Mathematics and Mathematical Sciences 13 (1) (2015), 15–37.

J. Kok and C. Susanth, Contemplating some invariants of the Jaco graph, Jn(1), n 2 N, Pioneer

Journal of Mathematics and Mathematical Sciences 13 (2) (2015), 67–138.

J. Kok and C. Susanth, Introduction to the McPherson number, (Upsilon(G)) of a simple connected graph, Pioneer Journal of Mathematics and Mathematical Sciences 13 (2) (2015), 91–102.

J. Kok, C. Susanth and S.J. Kalayathankal, Contemplating on Brush numbers of Mycielski Jaco graphs, ((mu)J_n(1)), (n in mathbb{N}), arXiv: 1501.01381v1 [math.CO], January 2015.

J. Kok, C. Susanth and S.J. Kalayathankal, A note on the Gutman index of Jaco graphs, $J_n(1)$, $ninmathbb{N}$, arXiv: 1502.07093v1 [math.CO], 25 February 2015 (submitted).

J. Kok, C. Susanth and S.J. Kalayathankal, Competition graphs of Jaco graphs and the introduction of the Grog number of a simple connected graph, Fundamental Journal of Mathematics and Mathematical Sciences 3 (1) (2015), 33–52.

J. Kok, C. Susanth and S.J. Kalayathankal, A study on linear Jaco graphs, Journal of Informatics and Mathematical Sciences 7 (2) (2015), 69–80.

J. Kok, N.K. Sudev and C. Sudev, Certain types of total irregularities of graphs and digraphs, arXiv: 1406.68634v3 [math.CO], 19 May 2015 (submitted).

J. Kok, N.K. Sudev and C. Sudev, The b-chromatic number of certain graphs and digraphs, arXiv: 1511.00680v1 [math.GM], 2 November 2015 (submitted).

J. Kok, C. Susanth and S.J. Kalayathankal, Brush numbers of certain Mycielski graphs, (submitted).

D. König, Theorie der endlichen und unenlichen Graphen, Akademische verlagsgesellschaft (1936).

S. McKeil, Chip firing cleaning process, M.Sc. Thesis, Dalhousie University (2007).

S.K. Merz, Competition Graphs, p-Competition Graphs, Two-Step Graphs, Squares and Domination Graphs, Ph.D. Thesis, University of Colorado at Denver, Department of Applied Mathematics (1995).

M.E. Messinger, Methods of Decontaminating a Network, Ph.D. Thesis, Dalhousie University (2008).

M.E. Messinger, R.J. Nowakowski and P. Pralat, Cleaning a network with brushes, Theoretical Computer Science 399 (2008), 191–205.

J. Mycielski, Sur le coloriages des graphes, Colloq. Maths. 3 (1955), 161–162.

C.W. Rasmussen, Interval Competition Graphs of Symmetric D-graphs and Two-Step Graphs of Trees, Ph.D. Thesis, University of Colorado at Denver, Department of Mathematics (1990).

A. Raychaudhuri, Intersection Assignments, T-colorings and Powers of Graphs, Ph.D. Thesis, Rutgers University (1987).

T. Ta Sheng, The Brush number of the two-dimensional torus, arXiv: 1012.4634v1 [math.CO], 21 December, 2010.

E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bulletin de la Société Royale des Sciences de Liège 41 (1972), 179–182.

Y.X. Zhu, L.H. You, J.S. Yang and Z. You, The maximal total irregularity of bicyclic graphs, Journal of Applied Mathematics 2014, Article ID 785084 (2014).

Y.X. Zhu, L.H. You and J.S. Yang, The minimal total irregularity of graphs, arXiv: 1404.0931v1 [math.CO], 3 April, 2014.




DOI: http://dx.doi.org/10.26713%2Fjims.v8i2.402

eISSN 0975-5748; pISSN 0974-875X