The \(m\)-Clique Load and the \(m\)-Clique Sequence of Graphs

Authors

  • Johan Kok Tshwane Metropolitan Police Department, City of Tshwane
  • G. Marimuthu Department of Mathematics, The Madura College, Madurai 625 011, Tamil Nadu

DOI:

https://doi.org/10.26713/jims.v8i3.396

Keywords:

\(m\)-clique, \(m\)-clique load, \(m\)-clique sequence, \(m\)-clique density

Abstract

This paper introduces the concepts of the \(m\)-clique load, the \(m\)-clique sequence and the \(m\)-clique density of graphs. The number of distinct maximum cliques over all maximal cliques is called the \(m\)-clique load of \(G\) and denoted, \(\diamond(G)\). The \(m\)-clique sequence denoted, \(\diamond\)-sequence of a graph \(G\) with \(\epsilon(G)\ge 1\) is the sequence with entries representing the number of maximal cliques of same order found in \(G\), in descending order. A finite sequence of positive integers each indexed with a distinct positive integer subscript which is \(c\)-graphical, is characterised. The \(m\)-clique density of a graph \(G\) denoted, \(p_{c_i}(G)\) is the probability of uniformly at random, choosing a maximal clique \(K_{c_i}\), \(1\le c_i\le \nu(G)\). Introductory results for certain graph classes and power graphs of balanced caterpillars, \(C^{\cal L}_{P_n}\) are also presented.

Downloads

Download data is not yet available.

References

H. Abdo and D. Dimitrov, The total irregularity of some composite graphs, International Journal of Computer Applications, 122 (21) (2015), pp. 1–9.

A.E. Andreev and S. Jukna, Very large cliques are easy to detect, Discrete Mathematics, 308 (2008), 3717–3721.

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

C. Bron and J. Kerbosch, Algorithm 457: Finding all cliques of an undirected graph, Communications of the ACM, 16 (9) (1973), pp. 575–579.

J.T. Gross and J. Yellen, Graph Theory and its Applications, CRC Press (2006).

B. Hedman, The maximum number of cliques in dense graphs, Discrete Mathematics, 54(1985), 161-166.

C. Hoede, Hard graphs for the maximum clique problem, Discrete Mathematics, 72 (1988), 175–179.

J. Kok, P. Fisher, B. Wilkens, M. Mabula and V. Mukungunugwa, Characteristics of Finite Jaco Graphs, Jn(1), n 2N, arXiv: 1404.0484v1 [math.CO], 2 April 2014.

J. Kok, K.P. Chithra, N.K. Sudev ad C. Susanth, A study on set-graphs, International Journal of Computer Applications, 118 (7) (May 2015), pp. 1–5.

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 K.P. Chithra, A study on edge-set graphs of certain graphs, International Journal of Computer Applications, 127 (6) (October 2015), pp. 1–5.

P.R.J. í–stergård, A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, 120 (2002), 197–207.

Downloads

Published

2016-12-01
CITATION

How to Cite

Kok, J., & Marimuthu, G. (2016). The \(m\)-Clique Load and the \(m\)-Clique Sequence of Graphs. Journal of Informatics and Mathematical Sciences, 8(3), 209–223. https://doi.org/10.26713/jims.v8i3.396

Issue

Vol. 8 No. 3 (2016)

Section

Research Articles

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.