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

Johan Kok, G. Marimuthu

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.

Keywords


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

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.26713%2Fjims.v8i3.396

eISSN 0975-5748; pISSN 0974-875X