Cliques Are Bricks for k-CT Graphs

Abstract

Many real networks in biology, chemistry, industry, ecological systems, or social networks have an inherent structure of simplicial complexes reflecting many-body interactions. Over the past few decades, a variety of complex systems have been successfully described as networks whose links connect interacting pairs of nodes. Simplicial complexes capture the many-body interactions between two or more nodes and generalized network structures to allow us to go beyond the framework of pairwise interactions. Therefore, to analyze the topological and dynamic properties of simplicial complex networks, the closed trail metric is proposed here. In this article, we focus on the evolution of simplicial complex networks from clicks and k-CT graphs. This approach is used to describe the evolution of real simplicial complex networks. We conclude with a summary of composition k-CT graphs (glued graphs); their closed trail distances are in a specified range.

1. Introduction

High-order cliques that are more complex than triangles enable a better understanding of complex networks. These structures improve our understanding of the clustering behavior of network structures concerning standard metrics. Yin et al. [1] measured the closure probability of higher-order network cliques using the introduced higher-order clustering coefficients. High-order closed trail clustering and closure coefficients were used [2] to evaluate a network structure. The why, how, and when of representations for complex systems were discussed [3]. Simplicial complexes were used for the representation of social contagion [4], for the modeling and analysis of biomolecules [5], and for big data processing [6]. The relevance of a simplicial community and higher-order connections’ quality in simplicial networks may be studied using centrality measures such as the simplicial degree centrality or the eigenvector centrality [7].

The analysis of large graphs is usually based on the study of two-connected components. The size of the components differs for different networks [8]. Unfortunately, this approach cannot be easily scaled, and it is difficult for weighted graphs. Another approach uses the cycles of a limited length, as suggested by Boruvka [9,10]. Our approach extends this principle to the limited-length cycles in the definition of two-connected components. Moreover, we describe building a graph or a network from the basic bricks—cliques. We demonstrate how to glue cliques and $k-CT$ graphs into larger graphs, and prove the properties of the glued graph based on the glueing.

Limited-length cycles are crucial in algebraic topology applications [11,12]; they are necessary to calculate the topological properties of data [13,14]. Moreover, cycles play important roles in other research areas such as in fullerenes in material science [15] and in complex and social networks [16].

The concept of limited-length cycles requires the measurement of the distances between nodes. The standard measure is the shortest path [17,18], but other approaches also exist [19,20,21,22]. The cyclical metric-based distance was introduced [23]. The distance between two vertices in a graph is defined as the shortest closed trail that contains these two vertices. The distance defined as such allows simple generalization for weighted graphs and allows scalability. The $k-CT$ components extracted using the cyclical metric can highlight the locally and cyclically connected subgraphs. Moreover, these components are not based on the biconnectivity property and may be used to partition densely connected biconnected components.

The remainder of this article is organized as follows: Section 2 introduces the terminology and the notation that are used in the article. The closed trail distance in biconnected undirected graphs and the construction of the $k-CT$ graphs by gluing graphs is then defined in Section 3. The advantages and limitations of $k-CT$ graphs are discussed in the Conclusions.

2. Terminology and Notation

This section contains the basic definition from graph theory required to fully understand the proposed approach The definitions of the following terms were mostly taken from [24].

A graph $G=(V,E)$ consists of two sets V and E, where the elements of V are vertices (or nodes) and the elements of $E\subseteq \left(\genfrac{}{}{0pt}{}{V}{2}\right)$ are edges. A walk on a graph is an alternating series of vertices and edges

$$W(v_0,v_k)=v_0{e}_1{v}_1{e}_2\dots v_{k-1}{e}_k{v}_k$$

such that, for $j=\{1,\dots ,k\}$, the vertices $v_{j-1}$ and $v_j$ are the end points of the edge $e_j$. A closed walk is a walk where the initial vertex is also the final vertex. The length of a walk is the number of edges in the walk. The length of a walk is denoted as $\left|W\right(u,v\left)\right|$. A trail is a walk in which no edge occurs more than once. A closed trail is a closed walk with no repeated edges. The closed trail that contains the vertex v and the edge e is denoted by $CT(v;e)$ (Figure 1), and the length of this closed trail is denoted by $\left|CT\right(v;e\left)\right|$. The closed trails that are specified by vertices $u,v$ or by vertices $u,v$ and edge e are denoted by $CT(u,v)$ or $CT(u,v;e)$. Other possibilities of denotation of closed trails are provided in Figure 1. A path is a walk in which no edge or internal vertex occurs more than once (a trail in which all the internal vertices are distinct). The shortest path with an initial vertex u and a final vertex v is denoted by $SP(u,v)$. A circuit is a closed trail. A cycle is a closed path with a length of at least one. A graph with k vertices and k edges, all in a single cycle, is denoted by $C_k$. A chord is an edge joining non-consecutive vertices of the cycle with a length greater than 3. A chordless cycle with a length greater than 3 is called a hole. A clique is a subgraph where each vertex is adjacent to every other vertex. A clique with k vertices is denoted by $Q_k$. The subclique is a subgraph induced by a subset of a vertices that forms a clique.

A connected graph is a graph where there is a walk between every pair of vertices. A biconnected graph is a connected and non-separable graph, meaning that if any vertex was to be removed, the graph would remain connected. A component of a graph is a maximal connected subgraph. An edge e is a bridge of the connected graph G, if and only if removing it disconnects the graph G. An articulation is a vertex of a graph whose removal increases the number of components. Therefore, a biconnected graph has no articulation vertices. A biconnected component is a maximal biconnected subgraph.

Any k-CT graph is denoted by $G^k$, and a set of k-CT graphs is denoted by ${\mathbb{G}}^k$.

3. Composition of k—CT Graphs from Cliques

This section describes the main contribution of the article. We demonstrate the principle of the composition of the graph using cliques and k-CT graphs, and prove the properties of the constructed graphs.

The construction of $k-CT$ graphs from cliques and $p-CT$ graphs with $p<k$ demonstrates the specific properties of these graphs. For example, a $6-CT$ graph can be a cycle with a length of 6, and this graph is sparse. However, a $6-CT$ graph can be a composite formed from two cliques connected via a vertex that has a high degree. This vertex is the hub in the network. The properties of the $6-CT$ graph depend on how the graph was created. These graphs can be described using simple complexes. For example, we can represent the situation in a co-author network where a group of authors collaborated on a particular article (Figure 2).

Definition 1

([25]). Let $n\ge 1$ be an integer and $V=\{v_1,...,v_n\}$ be a collection of n symbols. An (abstract) simplicial complex $\mathcal{K}$ on V or a complex is a collection of subsets of V, excluding ∅, such that

1. 

if $\sigma \in \mathcal{K}$ and $\tau \subset \sigma$, then $\tau \in \mathcal{K}$,

2. 

$\left\{v_i\right\}\in \mathcal{K}$ for every $v_i\in V$.

The set V is called the vertex set of $\mathcal{K}$, and the elements $\left\{v_i\right\}$ are called vertices or 0-simplices. We sometimes write $V\left(\mathcal{K}\right)$ for the vertex set of $\mathcal{K}$.

Definition 2

([3]). The clique complex $X\left(G\right)$ of a graph G is the simplicial complex with all complete subgraphs of G as its faces.

3.1. Closed Trail Distance in an Undirected Graph

We define a metric between the vertices in a biconnected graph without loops via a closed trail (circuit). This metric is applicable in connected graphs without bridges where, for every two vertices $u,v$, there exists a closed trail containing $u,v$.

Definition 3.

A graph $G=(V,E)$ is a k-closed trail connected graph (k-CT graph) if every two vertices lie on the closed trail (circuit) with a length $\le k$. The k-CT component of the graph is a maximal k-CT subgraph.

Definition 4.

Let $G=(V,E)$ be a graph. Let $d_{ct}:V\times V\to R_0^{+}$ be defined by the equation

$$d_{ct}(u,v)=mi{n}_{CT(u,v)\in G}\left|CT(u,v)\right|,$$

where $CT(u,v)$ is a closed trail that contains the vertices $u,v$. Then, the function $d_{ct}$ is called the closed trail connected distance ($CT$-distance).

Theorem 1.

The $CT$-distance is a metric on the set of vertices V in the graph $G=(V,E)$.

The proof of the theorem is provided in [23].

Lemma 1.

Every 3-CT component is a clique.

Proof. 

Let $u,v$ be arbitrary vertices in the 3-CT component. According to Definition 4, $d_{ct}(u,v)\le 3$. If $u\ne v$, then $CT(u,v)=u{e}_{1}v{e}_{2}w{e}_{3}u$ is the closed trail that contains the vertices $u,v$ and has a length equal to 3. It follows that the arbitrary vertices $u,v$ in the 3-CT component have to be adjacent and the 3-CT component is a clique. □

Lemma 2.

Any connected graph without bridges has $d_{ct}:V\times V\to R_0^{+}$ as a metric.

The proof of the lemma is provided in [23].

The extension of the $CT$-distance for a disconnected or connected graph with bridges is possible as follows:

Definition 5.

Let $G=(V,E)$ be a disconnected or connected graph with a bridge. If for vertices u and v, there is no closed trail containing these vertices, then the $CT$-distance between the vertices u and v is equal to ∞ ($d_{ct}(u,v)=\infty$).

3.2. Construction of $k-CT$ Graphs

The clique $Q_2$ is one of the elements that can be used to construct $k-CT$ graphs. This element does not contain a cycle and is always connected with other elements through both adjacent vertices. Then, it can be a part of a closed trail. Other cliques $Q_k$ for $k\ge 3$ contain triangles, and they can be connected with other elements via one vertex, via one edge, or via a selected subgraph.

Lemma 1 states that every clique is a 3-CT graph. How can we construct 4-CT graphs from cliques and how can we construct k-CT graphs for $k\ge 5$?

We define a glued graph of two graphs $G_1$ and $G_2$ via the isomorphic subgraphs $S_1$ and $S_2$. The subgraphs $S_1$ and $S_2$ can be arbitrary, but in this paper, they are cliques. Different studies have used different terminology: amalgamation of graphs [26], interface gluing [27], the glued graph between $G_1$ and $G_2$ at the clone H [28], or a similar k-clique-sum [29].

Definition 6.

Let graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ have subgraphs $S_1=(V_{S1},E_{S1})$ and $S_2=(V_{S2},E_{S2})$. A function $f:V_{S1}\to V_{S2}$ is a bijection such that if $(u,v)\in E_{S1}$, then $(f\left(u\right),f\left(v\right))\in E_{S2}$. This function is an isomorphism of subgraphs $S_1$ and $S_2$. The glued graph via isomorphism f is:

$$G_1{+}_f{G}_2=(V_1\bigsqcup V_2,E_1\bigsqcup E_2),$$

where $V_1\bigsqcup V_2=(V_1\backslash V_{S1})\bigcup V_2$, $E_1\bigsqcup E_2=(E_1\backslash E_{S1})\bigcup E_2$.

The glued graph is created from two graphs via the isomorphism $f:V_{S1}\to V_{S2}$ (see example in Figure 3.). We use abbreviations for more readable notation when the subgraphs are a vertex, edge, and clique with three or more vertices:

• $G_1{+}_v{G}_2$ when $f:\left\{v_1\right\}\to \left\{v_2\right\}$,
• $G_1{+}_e{G}_2$ when $f:\{u_1,v_1\}\to \{u_2,v_2\}$,
• $G_1{+}_{Q_p}{G}_2$ when $f:\{u_1^1,\dots ,u_1^p\}\to \{u_2^1,\dots ,u_2^p\}$.

Theorem 2.

Let $Q_k$ be cliques with k vertices. For a glued graph:

1. 

$Q_k{+}_v{Q}_l\in {\mathbb{G}}^6$ for $k,l\ge 3$,

2. 

$Q_k{+}_e{Q}_l\in {\mathbb{G}}^4$ for $k,l\ge 3$,

3. 

$Q_k{+}_{Q_p}{Q}_l\in {\mathbb{G}}^4$ for $1<p<k,l$ and $k,l\ge 3$.

Proof. 

• According to Lemma 1 $d_{ct}(u_1,v)\le 3$, $\forall u_1\in V\left(Q_k\right)$, $d_{ct}(u_2,v)\le 3$$\forall u_2\in V\left(Q_l\right)$, and $k,l\ge 3$. We consider the following situations in the glued graph $Q_k{+}_v{Q}_l$:

  (a)

  if $u_1=u_2$, then $d_{ct}(u_1,u_2)=0$;

  (b)

  if both vertices $u_1,u_2\in V\left(Q_k\right)$ or $u_1,u_2\in V\left(Q_l\right)$, then $d_{ct}(u_1,u_2)\le 3$;

  (c)

  if $v\ne u_1\in V\left(Q_k\right)$, $v\ne u_2\in V\left(Q_l\right)$, and $Q_k$ is glued with $Q_l$ via v, then $d_{ct}(u_1,u_2)=d_{ct}(u_1,v)+d_{ct}(u_2,v)=6$.

  From these situations, it follows that $Q_k{+}_v{Q}_l\in {\mathbb{G}}^6$.
• The gluing occurs via the edge $e=\{v,w\}$, where $e\in E\left(Q_k\right)$ and $e\in E\left(Q_l\right)$.

  (a)

  If $u_i=v$ or $u_i=w$, then $d_{ct}(u_1,u_2)\le 3$$\forall u_1,u_2\in V\left(Q_k{+}_e{Q}_l\right)$.

  (b)

  If both vertices $u_1,u_2\in V\left(Q_k\right)$ or $u_1,u_2\in V\left(Q_l\right)$, then $d_{ct}(u_1,u_2)\le 3$.

  (c)

  If $u_1\in V\left(Q_k\right)\backslash V\left(Q_p\right)$ and $u_2\in V\left(Q_l\right)\backslash V\left(Q_p\right)$, then $C_3(u_1,v,w,u_1)$ exists for all $u_1\in V\left(Q_k\right)\backslash V\left(Q_p\right)$, $v\ne u_1\ne w$ and $C_3^{\prime }(u_2,v,w,u_2)$ exists for all $u_2\in V\left(Q_l\right)\backslash V\left(Q_p\right)$, $v\ne u_2\ne w$. From the existence of two cycles with lengths equal to three that share a common edge follows the existence of $C_4(u_1,v,u_2,w,u_1)$, where the edge $e=\{v,w\}$ is the chord of cycle $C_4$ and $d_{CT}(u_1,u_2)=4$.

  From these situations, it follows that $Q_k{+}_e{Q}_l=\in {\mathbb{G}}^4$.
• The proof is similar to the previous situation where the graphs are glued via $Q_p$ with $p=2$.

  (a)

  If both vertices $u_1,u_2\in V\left(Q_p\right)$, then $d_{ct}(u_1,u_2)\le 3$.

  (b)

  If both vertices $u_1,u_2\in V\left(Q_k\right)$ or $u_1,u_2\in V\left(Q_l\right)$, then $d_{ct}(u_1,u_2)\le 3$.

  (c)

  If $u_1\in V\left(Q_k\right)\backslash V\left(Q_p\right)$ and $u_2\in V\left(Q_l\right)\backslash V\left(Q_p\right)$, then

  $d_{ct}(u_1,u_2)=\left|CT(u_1,v,u_2,w,u_1)\right|=4$, where $v,w\in V\left(Q_p\right)$.

  From these situations, it follows that $Q_k{+}_{Q_p}{Q}_l\in {\mathbb{G}}^4$.

□

The first part of Figure 4 demonstrates the glued graph from $Q_4$ and $Q_4^{\prime }$ via the vertex v. The middle part of Figure 4 demonstrates the glue of two cliques $Q_4$ and $Q_4^{\prime }$ via the common edge $\{v,w\}$. Dashed lines represent the shortest closed trail containing $u_1,u_2$. The third part of Figure 4 demonstrates the glue of two cliques $Q_5$ and $Q_5^{\prime }$ via the common clique $Q_3$ with $V\left(Q_3\right)=\{x,v,w\}$. Dashed lines represent the shortest closed trail containing the vertices $u_1,u_2$ in the glued graph.

Theorem 3.

Let $C_k$ be a single (chordless) cycle graph with length k; ${\mathbb{G}}^k$ is the set of k-CT graphs. For a cycle graph and a glued graph:

1. 

$C_k\in {\mathbb{G}}^k$ for $k\ge 3$,

2. 

$C_k{+}_v{C}_l\in {\mathbb{G}}^{k+l}$ for $k,l\ge 3$,

3. 

$C_k{+}_e{C}_l\in {\mathbb{G}}^{k+l-2}$ for $k,l\ge 3$, and

4. 

$Q_k{+}_e{C}_l\in {\mathbb{G}}^{l+1}$ for $k,l\ge 3$.

Proof. 

• It follows from Definition 3 of k-CT graphs that the CT distance between two different vertices of the cycle $C_k$ is k and $C_k\in {\mathbb{G}}^k$. The cycle $C_k$ is the sparsest k-CT graph.
• When we glue $C_k$ and $C_l$ cycle graphs so that they share one vertex v, then, from the properties of the cycles, it follows that: $d_{ct}(u_1,v)\le k$, $\forall u_1\in V\left(C_k\right)$ and $d_{ct}(u_2,v)\le l$, $\forall u_2\in V\left(C_l\right)$. The CT distance in the glued graph $C_k{+}_v{C}_l$ is $d_{ct}(u_1,u_2)=|CT(u_1,v,u_2)|=|C_k(u_1,v)|+|C_l(u_2,v)|\le k+l$ for all vertices $u_1$ in $C_k$ and for all vertices $u_2$ in $C_l$. Therefore, $C_k{+}_v{C}_l\in {\mathbb{G}}^{k+l}$.
• When we glue the $C_k$ and $C_l$ cycles so that they share one edge $e=\{v,w\}$, the resulting graph is a cycle with the chord e, and it has $k+l-2$ vertices. The CT distance is $d_{ct}(u_1,u_2)=\left|C_{k+l-2}(u_1,u_2)\right|=k+l-2$ for all vertices $u_1$ in $C_k$, where $v\ne u_1\ne w$, and for all vertices $u_2$ in $C_l$, where $v\ne u_2\ne w$. Other CT distances in the glued graph are smaller than $k+l-2$, and the glued graph is from the set ${\mathbb{G}}^{k+l-2}$.
• When we glue the $Q_k$ clique and $C_l$ cycle so that they share one edge $e=\{v,w\}$, then the resulting graph contains $k-2$ cycles with chord e and $l+1$ vertices. The CT distance is $d_{ct}(u_1,u_2)=\left|C_{l+1}(u_1,u_2)\right|=l+1$ for all vertices $u_1$ in $C_k$, where $v\ne u_1\ne w$, and for all vertices $u_2$ in $C_l$, where $v\ne u_2\ne w$. Other CT distances in the glued graph are smaller than $l+1$, and the glued graph is from the set ${\mathbb{G}}^{l+1}$.

□

Lemma 3.

For each $v\in V\left(G^k\right)$ and for each $e\in E\left(G^k\right)$, there exists $CT(v;e)$ in $G^k$ such that $\left|CT\right(v;e\left)\right|\le k+1$.

Proof. 

Let $e\in E\left(G^k\right)$, $e=\{u,w\}$, and $u,v,w\in V\left(G^k\right)$. From Definition 3, the existence of the shortest closed trails $CT(v,u)$ and $CT(v,w)$, such that $\left|CT\right(v,u\left)\right|\le k$ and $\left|CT\right(v,w\left)\right|\le k$ ( Figure 1), follows. Then, $\left|SP(v,u)\right|\le \frac{k}{2}$ and $\left|SP(v,w)\right|\le \frac{k}{2}$. For the shortest closed trail that contains the vertices $u,v,w$, the following apply:

• If $E\left(SP\right(v,u\left)\right)\cap E\left(SP\right(v,w\left)\right)=\varnothing$, then
  $\left|CT\right(v,u;e;w,v|\le |SP(v,u)|+1+|SP(w,v)|\le \frac{k}{2}+1+\frac{k}{2}\le k+1$;
• If $E\left(SP\right(v,u\left)\right)\cap E\left(SP\right(v,w\left)\right)\ne \varnothing$, then
  $CT(v;e)$ consists of $SP(v,u)$ or $SP(v,w)$, the edge e, and the rest of $CT(v,u)$ or $CT(v,w)$. In this situation: $\left|CT\right(v,u;e;w,v|\le min\{\left|SP\right(v,x\left)\right|+\left|CT\right(v,y)\backslash SP(v,y\left)\right|\}+1\le k+1$ where $x\in \{u,w\},y\in \{u,w\}\backslash \left\{x\right\}$.

□

Lemma 4.

3(4,5)-CT graphs do not contain articulation.

Proof. 

Proof by contradiction. Let some $G^k$ for $k\in \{3,4,5\}$ contain a vertex v, which is an articulation. Then, there exist vertices $u\ne w$ such that the shortest closed trail $CT(u,w)$ contains the articulation v, and the vertices $u,w$ are adjacent to the vertex v. For this shortest closed trail is true: $\left|CT(u,w)\right|=|CT(u,v,w,\dots ,z_1,v,z_2,\dots ,u)|\ge 6$. This contradicts the assumption that there is articulation in $G^k$ for $k\in \{3,4,5\}$. □

Theorem 4.

Let $G^4$ and $G^k$ be graphs with a specified CT distance. For a glued graph:

1. 

$G^4{+}_v{G}^k\in {\mathbb{G}}^r$, where $6\le r\le k+4$ for $k\in \{3,4,5\}$ and $k\le r\le k+4$ for $k\ge 6$;

2. 

$G^4{+}_e{G}^k\in {\mathbb{G}}^r$, where $4\le r\le k+4$ for $k\in \{3,4\}$ and $k\le r\le k+4$ for $k\ge 5$.

Proof. 

• The lower estimate of r:

  (a)

  Proof by contradiction. Let $G^4{+}_v{G}^k\in {\mathbb{G}}^r$ for $k\in \{3,4,5\}$ and $r<6$. There exist $u_1\in G^4$ and $u_2\in G^k$, such that $d_{CT}(u_1,v)\ge 3$ and $d_{CT}(u_2,v)\ge 3$. From the assumption, it follows that $d_{CT}(u_1,u_2)<6$, which is in contradiction with the CT distance between $u_1$ and $u_2$, which is longer than or equal to 6, which follows from Theorem 2 part 1.

  (b)

  It is obvious that for $k\ge 6$, $G^4{+}_v{G}^k\in {\mathbb{G}}^k$ is true.

  The upper estimate of r follows from Theorem 3 part 2.
• The lower estimate of r:

  (a)

  It is obvious that $r\ge 4$ for $k\in \{3,4\}$. It follows from Theorem 2 part 2.

  (b)

  The situation with $k\ge 5$ is obvious. The CT distance in a glued graph cannot be shorter than the CT distance in the part of the glued graph.

  The upper estimate of r follows from Lemma 3 and Theorem 3 part 3. An example of this situation is shown by the last image in Figure 5.

□

The examples in Figure 6 demonstrate different possibilities for $G^4{+}_v{G}^6$. The first part of Figure 6 demonstrates the lowest value of r and the third part demonstrates the highest value of r.

The examples in Figure 5 demonstrate different possibilities for $G^4{+}_e{G}^6$. The first part of Figure 6 demonstrates the lowest value of r and the third part demonstrates the highest value of r.

Generally, let $G^4=Q_p{+}_e{Q}_q$ and $G^k=C_m{+}_e{C}_n$, where $p,q,m,n\ge 3$ and $k=m+n-2$ (from Theorem 3, part 3). When we glue these glued graphs via the same edge e, then $G^4{+}_e{G}^k=Q_p{+}_e{Q}_q{+}_e{C}_m{+}_e{C}_n\in {\mathbb{G}}^r$ with $r=max\{m+1,n+1,k\}=k$ because $k-m=n-2\ge 3-2=1$ and $k-n=m-2\ge 3-2=1$. This corresponds to the first part of Figure 6.

Theorem 5.

Let $G^k$ and $G^l$ be graphs with a specified CT distance. For a glued graph:

1. 

$G^k{+}_v{G}^l\in {\mathbb{G}}^r$, where $6\le r\le (k+l)$ for each $k,l\in \{3,4,5,6\}$;

2. 

$G^k{+}_{Q_p}{G}^l\in {\mathbb{G}}^r$, where $max\{k,l\}\le r\le (k+l)$ for each [($k,l\ge 4$ and $p\ge 2$) or ($k,l\ge 7$ and $p=1$)].

Proof. 

• The lower estimate of r: A glued graph $G^r$ via the vertex v has the vertex v as an articulation. From Lemma 4, it follows that the $G^r$ with $r<6$ cannot contain articulation. The smallest r for the glued graph $G^r$ via the vertex v is 6. The upper estimate of r follows from Theorem 3 part 2.
• The lower estimate of r: From Definition 3 and Definition 6, it follows that it is impossible to obtain a glued graph $G^r=G^k{+}_{Q_p}{G}^l$ with $r<k$ and $r<l$. The upper estimate of r follows from Theorem 3 part 2.

□

The glued graph $G^k{+}_{Q_p}{G}^l$ via a clique can be realized using different methods as demonstrated in Figure 7.

4. Conclusions

This article demonstrates the construction of k-CT graphs from cliques and p-CT graphs where $p\le k$. These graphs correspond to simplicial complexes because the glueing is realized by a clique (in graph terminology) and face (in simplicial complex terminology). The discussed type of k-CT graphs (glued graphs) composition guarantees that their closed trail distances are within a specified range. This is valid for both types of data representation, as a graph or as a simplicial complex. The k-CT distance of the particular graph depends on the internal structure of the glued graphs.

The designed approach to constructing glued graphs can be used for modeling complex networks represented as simplicial complexes or graphs. Their k will be in the proved range and only in special cases will it be precise (examples in Figure 6 and Figure 7). Moreover, the proposed approach leads to some specific outcomes, such that the glueing of cliques via edges has the same properties as the glueing of cliques via subclique; both resulting graphs are from ${\mathbb{G}}^4$, but the glueing of cliques via vertexes is from ${\mathbb{G}}^6$. From this point of view, two persons in the social network that participate in the glueing of two cliques play the same role as the bigger subclique.

We presented the proposed approach, discussed the glueing of graphs concerning the k-CT distance, and studied the change in the structural properties of the original graphs and the glued one. We only considered cliques-faces and higher-order structures’ $k-CT$ components. The results provided in this article may be extended to other types of graphs.