Linear Jaco Graphs: A Critical Review
DOI:
https://doi.org/10.26713/jims.v8i2.402Keywords:
Linear Jaco graph, Hope graph, Jaconian vertex, Jaconian set, Fisher algorithm, Bettina's theorem.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.Downloads
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.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
