Introduction
For a (finite or infinite) connected graph G = ( V , E ) G = (V, E) G = ( V , E ) with ∣ V ∣ ≥ 2 |V| \ge2 ∣ V ∣ ≥ 2 the quadratic embedding constant (QEC for short), denoted by QEC ( G ) \operatorname{QEC}(G) QEC ( G ) , is defined to be the conditional supremum of the canonical quadratic function:
⟨ f , D f ⟩ = ∑ x , y ∈ V d G ( x , y ) f ( x ) f ( y ) , f ∈ C 0 ( V ) , \langle f, Df\rangle= \sum_{x,y \in V} d_G(x,y)f(x)f(y), \qquad f \in C_0(V), ⟨ f , D f ⟩ = x , y ∈ V ∑ d G ( x , y ) f ( x ) f ( y ) , f ∈ C 0 ( V ) ,
associated with the distance matrix D = [ d G ( x , y ) ] D = [d_G(x,y)] D = [ d G ( x , y )] of G G G subject to
⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 , f ∈ C 0 ( V ) , \langle f,f\rangle= 1,\qquad\langle\mathbf{1},f\rangle= 0,\qquad f \in C_0(V), ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 , f ∈ C 0 ( V ) ,
where C 0 ( V ) C_0(V) C 0 ( V ) is the space of real column vectors f = [ f ( x ) ] x ∈ V f = [f(x)]_{x\in V} f = [ f ( x ) ] x ∈ V with finite supports, 1 ∈ C ( V ) \mathbf{1} \in C(V) 1 ∈ C ( V ) is the all-one column vector, and ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ the canonical inner product. If G G G is finite, the conditional supremum is attained at some f ∈ C ( V ) = C 0 ( V ) f \in C(V) = C_0(V) f ∈ C ( V ) = C 0 ( V ) so that we may write
QEC ( G ) = max { ⟨ f , D f ⟩ ; f ∈ C ( V ) , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 } . (1) \operatorname{QEC}(G) = \max\{\langle f,Df\rangle;\ f\in C(V),\ \langle f,f\rangle= 1,\ \langle\mathbf{1},f\rangle= 0\}. \tag*{(1)} QEC ( G ) = max {⟨ f , D f ⟩ ; f ∈ C ( V ) , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 } . (1)
The QEC becomes a numeric invariant of connected graphs on two or more vertices, and takes values in [ − 1 , + ∞ ) [-1,+\infty) [ − 1 , + ∞ ) .
Since the QEC was introduced in [35 ] , research interest in it has steadily increased, with most studies focusing on finite graphs; see [34 ] for a comprehensive survey of recent results. Concrete values of QEC are known for some special classes of graphs, e.g., paths [25 ] , fan graphs [27 , 28 ] , theta graphs [29 , 42 ] , wheels [31 ] and others [17 , 37 ] . Formulas and estimates for QEC under various graph operations have also been investigated, e.g., for cluster graphs [10 ] , corona graphs [13 ] , graph joins [21 ] , star products [26 ] , lexicographic products [30 ] , and so on. The investigation of graphs with a positive QEC has only recently begun [29 , 32 , 33 ] . The classification of graphs in terms of QEC remains a central open problem, though progress has been limited so far, see [4 , 5 ] . In this paper we present a result that is expected to constitute an important step toward this goal.
The most fundamental fact that motivated the introduction of the QEC comes from the famous works of Schoenberg [40 , 41 ] . Let G = ( V , E ) G = (V,E) G = ( V , E ) be a (finite or infinite) connected graph and H \mathcal{H} H a Hilbert space. A map φ : V → H \varphi: V \to\mathcal{H} φ : V → H is called a quadratic embedding of G G G if
∥ φ ( x ) − φ ( y ) ∥ 2 = d G ( x , y ) , x , y ∈ V , \lVert\varphi(x)-\varphi(y)\rVert^2 = d_G(x,y),\qquad x,y\in V, ∥ φ ( x ) − φ ( y ) ∥ 2 = d G ( x , y ) , x , y ∈ V ,
where ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ stands for the norm of H \mathcal{H} H . The concept of quadratic embedding has been developed into a central one along with the Euclidean distance geometry [1 , 3 , 18 , 19 , 20 ] . In our terminology we recall the following
Theorem 1.1 (Schoenberg). For a (finite or infinite) connected graph G = ( V , E ) G = (V,E) G = ( V , E ) with ∣ V ∣ ≥ 2 |V| \ge2 ∣ V ∣ ≥ 2 the following three conditions are equivalent:
G G G admits a quadratic embedding;
the distance matrix D D D of G G G is conditionally negative definite, i.e., ⟨ f , D f ⟩ ≤ 0 \langle f,Df\rangle\le0 ⟨ f , D f ⟩ ≤ 0 for any f ∈ C 0 ( V ) f \in C_0(V) f ∈ C 0 ( V ) with ⟨ 1 , f ⟩ = 0 \langle\mathbf{1},f\rangle= 0 ⟨ 1 , f ⟩ = 0 ;
QEC ( G ) ≤ 0 \operatorname{QEC}(G) \le0 QEC ( G ) ≤ 0 .
The essential point lies in the equivalence (i) ⇔ \Leftrightarrow ⇔ (ii), which was first proved in the seminal works of Schoenberg [40 , 41 ] , while the equivalence (ii) ⇔ \Leftrightarrow ⇔ (iii) is verified easily from the definition of the QEC. As a result, the QEC allows us to determine numerically whether a connected graph admits a quadratic embedding. In this context, we will determine the class of graphs with QEC ( G ) < − 1 / 2 \operatorname{QEC}(G) < -1/2 QEC ( G ) < − 1/2 , which represents the first non-trivial achievement after Schoenberg’s result (Theorem 1.1). We will prove the following
Theorem 1.2. Let G = ( V , E ) G = (V,E) G = ( V , E ) be a finite connected graph with ∣ V ∣ ≥ 2 |V| \ge2 ∣ V ∣ ≥ 2 . Then the following conditions are equivalent:
(i) G G G is cactus-like, that is, every pair of distinct maximal cliques has at most one vertex in common and the clique graph Γ ( G ) \Gamma(G) Γ ( G ) is a tree;
(ii) G G G is a block graph whose clique graph Γ ( G ) \Gamma(G) Γ ( G ) is a tree;
(iii) QEC ( G ) < − 1 / 2 \operatorname{QEC}(G) < -1/2 QEC ( G ) < − 1/2 .
A cactus-like graph was introduced in the recent paper [5 ] , where the implication (iii) ⇒ \Rightarrow ⇒ (i) was proved. The main contribution of this paper is the converse (i) ⇒ \Rightarrow ⇒ (iii), which has been left open. Meanwhile, the equivalence (i) ⇔ \Leftrightarrow ⇔ (ii), which can be verified directly by definition, provides a clear structural characterization of cactus-like graphs. To gain an intuitive understanding of a cactus-like graph, an example is given in Figure 1 .
Figure 1. Cactus-like graph G G G and its clique graph Γ ( G ) \Gamma(G) Γ ( G )
In the proof of the implication (i) ⇒ \Rightarrow ⇒ (iii), two results play a key role. One is a generalization of a result on the length function of trees or of free product groups studied within harmonic analysis [22 , 23 , 24 , 44 ] . The other is a technical estimate of QEC of star products obtained in [4 ] . Thus, our study of QEC of block graphs led us to a link of harmonic analysis on free products. Moreover, determining the infinite connected graphs that satisfy QEC ( G ) < − 1 / 2 \operatorname{QEC}(G) < -1/2 QEC ( G ) < − 1/2 is an interesting open question and the subject of ongoing research.
This paper is organized as follows. In § 2 we recall some notions and notations of graphs in relation to QEC, and assemble some known results necessary for our goal. In § 3 we describe some properties of block graphs and introduce cactus-like graphs in this context. In particular, we obtain equivalent conditions for a graph to be cactus-like (Proposition 3.14 ), from which we see that two conditions (i) and (ii) in Theorem 1.2 are equivalent. In § 4 we derive upper and lower bounds for QEC of a block graph and complete the proof of Theorem 1.2 . The upper bound of QEC of a finite block graph with two or more maximal cliques is also noteworthy (Theorem 4.4 ). In § 5 we prove the key result on conditionally negative definite matrices on a block graph (Theorem 4.1 ), which plays an essential role in the proof of the main result. The proof proceeds by constructing a conditionally negative definite kernel by concatenating local ones along geodesics in a block graph. This method is an extension of a similar idea established for trees and Cayley graphs of free product groups [24 ] . In Section 6 we discuss trees and free products of complete graphs as special cases and make some comments. In Appendix we review the formula for QEC of a star product of complete graphs, which is used for the lower bound for QEC of a block graph.
Preliminaries
Graphs and Subgraphs
A graph is a pair G = ( V , E ) G=(V,E) G = ( V , E ) consisting of a non-empty set V V V and a subset of the two-element subsets of V V V . An element of V V V is called a vertex and an element of E E E an edge . A graph G = ( V , E ) G=(V,E) G = ( V , E ) is called finite if V V V is a (non-empty) finite set, and infinite otherwise. In this paper we deal with both finite and infinite graphs.
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. Two vertices x , y ∈ V x,y\in V x , y ∈ V are called adjacent if { x , y } ∈ E \{x,y\}\in E { x , y } ∈ E . In that case, we write x ∼ y x\sim y x ∼ y as usual. Note that this definition of a graph precludes loops, that is, x ≁ x x\not\sim x x ∼ x . For any x , y ∈ V x,y\in V x , y ∈ V a finite sequence of vertices x 0 , x 1 , … , x m ∈ V x_0,x_1,\ldots,x_m\in V x 0 , x 1 , … , x m ∈ V such that
x = x 0 ∼ x 1 ∼ ⋯ ∼ x m = y , (2) x=x_0\sim x_1\sim\cdots\sim x_m=y, \tag*{(2)} x = x 0 ∼ x 1 ∼ ⋯ ∼ x m = y , (2)
where m ≥ 0 m\ge0 m ≥ 0 and some of x 0 , x 1 , … , x m x_0,x_1,\ldots,x_m x 0 , x 1 , … , x m may coincide, is called a walk of length m m m connecting x x x and $y. If x 0 , x 1 , … , x m x_0,x_1,\ldots,x_m x 0 , x 1 , … , x m are mutually distinct, the walk in (2) is called a path of length m m m . If m ≥ 3 m\ge3 m ≥ 3 , x = y x=y x = y , and x 0 , x 1 , … , x m − 1 x_0,x_1,\ldots,x_{m-1} x 0 , x 1 , … , x m − 1 are mutually distinct, then the walk in (2) is called a cycle of length m m m .
A graph G = ( V , E ) G=(V,E) G = ( V , E ) is called connected if any two vertices x , y ∈ V x,y\in V x , y ∈ V are connected by a walk. In that case, the length of a shortest walk (equivalently, a shortest path) connecting x x x and y y y is called the graph distance between x x x and y y y , and is denoted by d G ( x , y ) d_G(x,y) d G ( x , y ) or simply by d ( x , y ) d(x,y) d ( x , y ) when there is no risk of confusion.
Let G = ( V , E ) G=(V,E) G = ( V , E ) and H = ( W , F ) H=(W,F) H = ( W , F ) be two graphs. We say that H H H is a subgraph of G G G and write H ⊂ G H\subset G H ⊂ G if W ⊂ V W\subset V W ⊂ V and F ⊂ E F\subset E F ⊂ E . A subgraph H = ( W , F ) H=(W,F) H = ( W , F ) of G = ( V , E ) G=(V,E) G = ( V , E ) is called an induced subgraph if F = E ↾ W F=E\mathord{\upharpoonright}_W F = E ↾ W holds, that is, for any x , y ∈ W x,y\in W x , y ∈ W we have { x , y } ∈ F ⟺ { x , y } ∈ E \{x,y\}\in F\Longleftrightarrow\{x,y\}\in E { x , y } ∈ F ⟺ { x , y } ∈ E . In that case we also say that H H H is the subgraph induced by W W W , and write H = ⟨ W ⟩ H=\langle W\rangle H = ⟨ W ⟩ .
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a connected graph and H = ( W , F ) H=(W,F) H = ( W , F ) a connected subgraph of G G G . Let d G d_G d G and d H d_H d H be the graph distances of G G G and H H H , respectively. We say that H H H is an isometric subgraph of G G G if
d H ( x , y ) = d G ( x , y ) , x , y ∈ W . (3) d_H(x,y)=d_G(x,y),\qquad x,y\in W. \tag*{(3)} d H ( x , y ) = d G ( x , y ) , x , y ∈ W . (3)
An isometric subgraph is necessarily an induced subgraph, but the converse is false.
Quadratic Embedding Constant
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a connected graph with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 and d ( x , y ) d(x,y) d ( x , y ) the graph distance between two vertices x x x and y y y in V V V . Recall that G G G may be finite or infinite. Let C ( V ) C(V) C ( V ) be the space of real column vectors f = [ f ( x ) ] x ∈ V f=[f(x)]_{x\in V} f = [ f ( x ) ] x ∈ V and C 0 ( V ) C_0(V) C 0 ( V ) its subspace of those with finite supports, that is, those f = [ f ( x ) ] f=[f(x)] f = [ f ( x )] with f ( x ) = 0 f(x)=0 f ( x ) = 0 except finitely many x ∈ V x\in V x ∈ V .
The canonical quadratic function associated to the distance matrix D = [ d ( x , y ) ] x , y ∈ V D=[d(x,y)]_{x,y\in V} D = [ d ( x , y ) ] x , y ∈ V of G G G is defined by
⟨ f , D f ⟩ = ∑ x , y ∈ V d ( x , y ) f ( x ) f ( y ) , f ∈ C 0 ( V ) , (4) \langle f,Df\rangle=\sum_{x,y\in V}d(x,y)f(x)f(y),\qquad f\in C_0(V), \tag*{(4)} ⟨ f , D f ⟩ = x , y ∈ V ∑ d ( x , y ) f ( x ) f ( y ) , f ∈ C 0 ( V ) , (4)
where ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ stands for the canonical inner product on C 0 ( V ) C_0(V) C 0 ( V ) . The quadratic embedding constant (QEC for short) of G G G is the conditional supremum of ⟨ f , D f ⟩ \langle f,Df\rangle ⟨ f , D f ⟩ defined by
QEC ( G ) = sup { ⟨ f , D f ⟩ ; f ∈ C 0 ( V ) , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 } , (5) \operatorname{QEC}(G)=\sup\{\langle f,Df\rangle;\ f\in C_0(V),\ \langle f,f\rangle=1,\ \langle\mathbf{1},f\rangle=0\}, \tag*{(5)} QEC ( G ) = sup {⟨ f , D f ⟩ ; f ∈ C 0 ( V ) , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 } , (5)
where 1 ∈ C ( V ) \mathbf{1}\in C(V) 1 ∈ C ( V ) is the column vector whose entries are all one and ⟨ 1 , f ⟩ \langle\mathbf{1},f\rangle ⟨ 1 , f ⟩ is understood as a natural extension of the inner product on C 0 ( V ) C_0(V) C 0 ( V ) . If G = ( V , E ) G=(V,E) G = ( V , E ) is a finite connected graph with ∣ V ∣ = n ≥ 2 |V|=n\ge2 ∣ V ∣ = n ≥ 2 , we have C ( V ) = C 0 ( V ) ≅ R n C(V)=C_0(V)\cong\mathbb{R}^{n} C ( V ) = C 0 ( V ) ≅ R n and QEC ( G ) \operatorname{QEC}(G) QEC ( G ) is attained at some f ∈ C ( V ) f\in C(V) f ∈ C ( V ) satisfying ⟨ f , f ⟩ = 1 \langle f,f\rangle=1 ⟨ f , f ⟩ = 1 and ⟨ 1 , f ⟩ = 0 \langle\mathbf{1},f\rangle=0 ⟨ 1 , f ⟩ = 0 . Hence, (2.4) becomes
QEC ( G ) = max { ⟨ f , D f ⟩ ; f ∈ C ( V ) , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 } , (6) \operatorname{QEC}(G)=\max\{\langle f,Df\rangle;\ f\in C(V),\ \langle f,f\rangle=1,\ \langle\mathbf{1},f\rangle=0\}, \tag*{(6)} QEC ( G ) = max {⟨ f , D f ⟩ ; f ∈ C ( V ) , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 } , (6)
as stated in Introduction. The QEC is a numeric invariant of connected graphs on two or more vertices.
The following result, the proof of which is straightforward from definition, will be used freely without further comment.
Proposition 2.1 ([35 ] ). Let G = ( V , E ) G=(V,E) G = ( V , E ) be a connected graph and H = ( W , F ) H=(W,F) H = ( W , F ) its isometric subgraph with ∣ W ∣ ≥ 2 |W|\ge2 ∣ W ∣ ≥ 2 . Then we have QEC ( H ) ≤ QEC ( G ) \operatorname{QEC}(H)\le\operatorname{QEC}(G) QEC ( H ) ≤ QEC ( G ) .
The set of integers Z = { … , − 2 , − 1 , 0 , 1 , 2 , … } \mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\} Z = { … , − 2 , − 1 , 0 , 1 , 2 , … } equipped with the natural adjacency relation i ∼ i + 1 i\sim i+1 i ∼ i + 1 becomes an (infinite) graph called the two-sided infinite path and is denoted by Z \mathbb{Z} Z for simplicity. The subgraph induced by { 0 , 1 , 2 , … } \{0,1,2,\ldots\} { 0 , 1 , 2 , … } is called the one-sided infinite path and denoted by Z + \mathbb{Z}_+ Z + .
Proposition 2.2 ([25 , 26 ] ). It holds that
lim n → ∞ QEC ( P n ) = QEC ( Z + ) = QEC ( Z ) = − 1 2 , \lim_{n\to\infty}\operatorname{QEC}(P_n)=\operatorname{QEC}(\mathbb{Z}_+)=\operatorname{QEC}(\mathbb{Z})=-\frac{1}{2}, n → ∞ lim QEC ( P n ) = QEC ( Z + ) = QEC ( Z ) = − 2 1 , where P n P_n P n is a path graph on n n n vertices.
The original proof [26 ] requires a precise estimate of QEC ( P n ) \operatorname{QEC}(P_n) QEC ( P n ) without knowing its explicit value. Subsequently, the explicit value
QEC ( P n ) = − 1 1 + cos π / n , n = 2 , 3 , … , \operatorname{QEC}(P_n)=-\frac{1}{1+\cos\pi/n},\qquad n=2,3,\ldots, QEC ( P n ) = − 1 + cos π / n 1 , n = 2 , 3 , … ,
was determined through a skillful analysis of a certain determinant [25 ] .
Following general notation of graph theory, a finite graph on n ≥ 1 n \ge1 n ≥ 1 vertices is called complete if every pair of distinct vertices is adjacent, and such a graph is denoted by K n K_n K n as usual. To avoid ambiguity, we always use the term ‘complete graph’ exclusively for finite graphs, and refer to an infinite graph in which every pair of distinct vertices is adjacent as an ‘infinite complete graph’ to distinguish it from the former. An infinite complete graph is denoted by K ∞ K_\infty K ∞ , regardless of the cardinality of the vertex set. The distinction between infinite cardinalities plays no role throughout this paper.
Proposition 2.3. It holds that
QEC ( K n ) = QEC ( K ∞ ) = − 1 , n ≥ 2. \operatorname{QEC}(K_n) = \operatorname{QEC}(K_\infty) = -1, \qquad n \ge2. QEC ( K n ) = QEC ( K ∞ ) = − 1 , n ≥ 2. In fact, for a finite or infinite complete graph G = ( V , E ) G = (V,E) G = ( V , E ) with distance matrix D D D we have ⟨ f , D f ⟩ = − 1 \langle f,Df\rangle= -1 ⟨ f , D f ⟩ = − 1 for any f ∈ C 0 ( V ) f \in C_0(V) f ∈ C 0 ( V ) with ⟨ f , f ⟩ = 1 \langle f,f\rangle= 1 ⟨ f , f ⟩ = 1 and ⟨ 1 , f ⟩ = 0 \langle1,f\rangle= 0 ⟨ 1 , f ⟩ = 0 .
Star Products
A graph G = ( V , E ) G = (V,E) G = ( V , E ) equipped with a distinguished vertex o ∈ V o \in V o ∈ V is called a rooted graph with a root o o o and is denoted by ( G , o ) = ( V , E , o ) (G,o) = (V,E,o) ( G , o ) = ( V , E , o ) . For two rooted graphs ( G 1 , o 1 ) = ( V 1 , E 1 , o 1 ) (G_1,o_1) = (V_1,E_1,o_1) ( G 1 , o 1 ) = ( V 1 , E 1 , o 1 ) and ( G 2 , o 2 ) = ( V 2 , E 2 , o 2 ) (G_2,o_2) = (V_2,E_2,o_2) ( G 2 , o 2 ) = ( V 2 , E 2 , o 2 ) with V 1 ∩ V 2 = ∅ V_1 \cap V_2 = \varnothing V 1 ∩ V 2 = ∅ the graph obtained by gluing their roots is called the star product of ( G 1 , o 1 ) (G_1,o_1) ( G 1 , o 1 ) and ( G 2 , o 2 ) (G_2,o_2) ( G 2 , o 2 ) , and is denoted by ( G 1 , o 1 ) ⋆ ( G 2 , o 2 ) (G_1,o_1) \star(G_2,o_2) ( G 1 , o 1 ) ⋆ ( G 2 , o 2 ) . If there is no danger of confusion, we omit reference to the roots o 1 o_1 o 1 and o 2 o_2 o 2 .
Proposition 2.4 ([35 ] ). Let G 1 G_1 G 1 and G 2 G_2 G 2 be connected rooted graphs on two or more vertices, and let G 1 ⋆ G 2 G_1 \star G_2 G 1 ⋆ G 2 be their star product. Then we have
max { QEC ( G 1 ) , QEC ( G 2 ) } ≤ QEC ( G 1 ⋆ G 2 ) . \max\{\operatorname{QEC}(G_1),\operatorname{QEC}(G_2)\} \le\operatorname{QEC}(G_1 \star G_2). max { QEC ( G 1 ) , QEC ( G 2 )} ≤ QEC ( G 1 ⋆ G 2 ) . Moreover, if QEC ( G 1 ) ≤ 0 \operatorname{QEC}(G_1) \le0 QEC ( G 1 ) ≤ 0 and QEC ( G 2 ) ≤ 0 \operatorname{QEC}(G_2) \le0 QEC ( G 2 ) ≤ 0 , we have
QEC ( G 1 ⋆ G 2 ) ≤ 0. \operatorname{QEC}(G_1 \star G_2) \le0. QEC ( G 1 ⋆ G 2 ) ≤ 0.
The first half is immediate from Proposition 2.1 since both G 1 G_1 G 1 and G 2 G_2 G 2 are isometric subgraphs of G 1 ⋆ G 2 G_1 \star G_2 G 1 ⋆ G 2 . The second half is proved by constructing a quadratic embedding map of G 1 ⋆ G 2 G_1 \star G_2 G 1 ⋆ G 2 , see also [26 ] for a computational proof. It is an interesting problem to obtain precise estimate of QEC ( G 1 ⋆ G 2 ) \operatorname{QEC}(G_1 \star G_2) QEC ( G 1 ⋆ G 2 ) for two connected graphs G 1 G_1 G 1 and G 2 G_2 G 2 with QEC ( G 1 ) < 0 \operatorname{QEC}(G_1) < 0 QEC ( G 1 ) < 0 and QEC ( G 2 ) < 0 \operatorname{QEC}(G_2) < 0 QEC ( G 2 ) < 0 . In this connection the following result is useful to our goal.
Proposition 2.5 ([4 ] ). Let G = ( V , E ) G = (V,E) G = ( V , E ) be a finite connected graph with ∣ V ∣ ≥ 2 |V| \ge2 ∣ V ∣ ≥ 2 with QEC ( G ) < 0 \operatorname{QEC}(G) < 0 QEC ( G ) < 0 . Let o ∈ V o \in V o ∈ V . If there exists f ∈ C ( V ) f \in C(V) f ∈ C ( V ) satisfying
QEC ( G ) = ⟨ f , D f ⟩ , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 , f ( o ) ≠ 0 , \operatorname{QEC}(G) = \langle f,Df\rangle,\qquad\langle f,f\rangle= 1,\qquad\langle1,f\rangle= 0,\qquad f(o) \ne0, QEC ( G ) = ⟨ f , D f ⟩ , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0 , f ( o ) = 0 , then for any k ≥ 2 k \ge2 k ≥ 2 we have
QEC ( G ) < QEC ( ( G , o ) ⋆ K k ) < 0 , \operatorname{QEC}(G) < \operatorname{QEC}((G,o) \star K_k) < 0, QEC ( G ) < QEC (( G , o ) ⋆ K k ) < 0 , where K k K_k K k is the complete graph on k k k vertices and its root is chosen arbitrarily.
Block Graphs
Our terminology concerning block graphs follows standard textbooks [2 , 8 ] , see also [15 ] for the original idea of Harary. Although many references restrict their attention to finite graphs, this paper also considers infinite graphs. To avoid any ambiguity arising from this broader setting, we provide some explanations, even at the expense of some redundancy. Recall that throughout this paper, the term ‘graph’ refers to either a finite or an infinite graph.
2-Connected Components
A connected graph G = ( V , E ) G=(V,E) G = ( V , E ) is called 2 2 2 -connected if the induced subgraph G ∖ { x } = ⟨ V ∖ { x } ⟩ G\setminus\{x\}=\langle V\setminus\{x\}\rangle G ∖ { x } = ⟨ V ∖ { x }⟩ remains connected for any x ∈ V x\in V x ∈ V . By definition, the singleton graph K 1 K_1 K 1 is connected but not 2 2 2 -connected, while the complete graph K n K_n K n on n ≥ 2 n\ge2 n ≥ 2 vertices is 2 2 2 -connected. A 2 2 2 -connected subgraph H = ( W , F ) H=(W,F) H = ( W , F ) of a graph G G G is called a 2 2 2 -connected component if there is no 2 2 2 -connected subgraph H 1 H_1 H 1 of G G G such that H ⊂ H 1 H\subset H_1 H ⊂ H 1 and H ≠ H 1 H\ne H_1 H = H 1 . A 2 2 2 -connected component is necessarily an induced subgraph.
The following assertions follow directly from the definitions via elementary arguments.
Lemma 3.1. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. Let H 1 = ( W 1 , F 1 ) H_1=(W_1,F_1) H 1 = ( W 1 , F 1 ) and H 2 = ( W 2 , F 2 ) H_2=(W_2,F_2) H 2 = ( W 2 , F 2 ) be 2 2 2 -connected subgraphs of G G G . If ∣ W 1 ∩ W 2 ∣ ≥ 2 \lvert W_1\cap W_2\rvert\ge2 ∣ W 1 ∩ W 2 ∣ ≥ 2 , then H 1 ∪ H 2 = ( W 1 ∪ W 2 , F 1 ∪ F 2 ) H_1\cup H_2=(W_1\cup W_2,F_1\cup F_2) H 1 ∪ H 2 = ( W 1 ∪ W 2 , F 1 ∪ F 2 ) is also a 2 2 2 -connected subgraph of G G G .
Lemma 3.2. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. Any 2 2 2 -connected subgraph H 0 H_0 H 0 of G G G is contained in a unique 2 2 2 -connected component. In particular, any edge of G G G is contained in a unique 2 2 2 -connected component.
Lemma 3.3. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. For any distinct 2 2 2 -connected components H 1 = ( W 1 , F 1 ) H_1=(W_1,F_1) H 1 = ( W 1 , F 1 ) and H 2 = ( W 2 , F 2 ) H_2=(W_2,F_2) H 2 = ( W 2 , F 2 ) we have ∣ W 1 ∩ W 2 ∣ ≤ 1 \lvert W_1\cap W_2\rvert\le1 ∣ W 1 ∩ W 2 ∣ ≤ 1 .
Maximal Cliques and Clique Graphs
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. A non-empty (finite or infinite) subset C ⊂ V C\subset V C ⊂ V is called a clique of G G G if every pair of distinct vertices in C C C is adjacent, or equivalently if ⟨ C ⟩ \langle C\rangle ⟨ C ⟩ is a finite or infinite complete graph. By a slight abuse of notation, the term ‘clique’ may also refer to the subgraph it induces.
Lemma 3.4. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. Let H = ( W , F ) H=(W,F) H = ( W , F ) be a 2 2 2 -connected component and C ⊂ V C\subset V C ⊂ V a clique. If ∣ W ∩ C ∣ ≥ 2 \lvert W\cap C\rvert\ge2 ∣ W ∩ C ∣ ≥ 2 , we have C ⊂ W C\subset W C ⊂ W .
Proof. From ∣ W ∩ C ∣ ≥ 2 \lvert W\cap C\rvert\ge2 ∣ W ∩ C ∣ ≥ 2 we see that ⟨ C ⟩ \langle C\rangle ⟨ C ⟩ is a finite or infinite complete graph on two or more vertices, hence is 2 2 2 -connected. It then follows by Lemma 3.1 that H ∪ ⟨ C ⟩ H\cup\langle C\rangle H ∪ ⟨ C ⟩ is a 2 2 2 -connected subgraph of G G G . But since H H H is a maximal 2 2 2 -connected subgraph by assumption, we have H = H ∪ ⟨ C ⟩ H=H\cup\langle C\rangle H = H ∪ ⟨ C ⟩ , which implies that W = W ∪ C W=W\cup C W = W ∪ C , that is, C ⊂ W C\subset W C ⊂ W .
A clique of a graph G = ( V , E ) G=(V,E) G = ( V , E ) is called maximal if it is maximal in the family of cliques with respect to the set inclusion relation. The following assertion is obvious for a finite graph G G G ; however, for a general infinite graph G G G , we need to invoke the Kuratowski–Zorn lemma.
Lemma 3.5. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. For any clique C 0 C_0 C 0 of G G G there exists a maximal clique C C C such that C 0 ⊂ C C_0 \subset C C 0 ⊂ C . In particular, any vertex as well as any edge is contained in at least one maximal clique.
The set C \mathcal{C} C of all maximal cliques of a graph G G G induces a graph, where two distinct maximal cliques C 1 , C 2 ∈ C C_1,C_2\in\mathcal{C} C 1 , C 2 ∈ C are defined to be adjacent if C 1 ∩ C 2 ≠ ∅ C_1\cap C_2\ne\varnothing C 1 ∩ C 2 = ∅ . The graph thus obtained is called the clique graph of G G G , and is denoted by Γ ( G ) \Gamma(G) Γ ( G ) .
Lemma 3.6. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. Then the clique graph Γ ( G ) \Gamma(G) Γ ( G ) is connected if and only if so is G G G .
The proof follows directly from the observation that any edge of G G G is contained in a maximal clique, see Lemma 3.5. For later convenience, we mention some detailed results on paths in G G G and in Γ ( G ) \Gamma(G) Γ ( G ) .
Lemma 3.7. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph and m ≥ 1 m\ge1 m ≥ 1 . Let x 0 ∼ x 1 ∼ ⋯ ∼ x m x_0\sim x_1\sim\cdots\sim x_m x 0 ∼ x 1 ∼ ⋯ ∼ x m be a shortest path in G G G connecting x 0 x_0 x 0 and x m x_m x m . For i = 1 , 2 , … , m i=1,2,\ldots,m i = 1 , 2 , … , m let C i C_i C i be a maximal clique containing { x i − 1 , x i } \{x_{i-1},x_i\} { x i − 1 , x i } . Then C 1 ∼ C 2 ∼ ⋯ ∼ C m C_1\sim C_2\sim\cdots\sim C_m C 1 ∼ C 2 ∼ ⋯ ∼ C m is a shortest path in Γ ( G ) \Gamma(G) Γ ( G ) connecting C 1 C_1 C 1 and C m C_m C m .
Lemma 3.8. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph and m ≥ 1 m\ge1 m ≥ 1 . Let C 0 ∼ C 1 ∼ ⋯ ∼ C m C_0\sim C_1\sim\cdots\sim C_m C 0 ∼ C 1 ∼ ⋯ ∼ C m be a shortest path connecting C 0 C_0 C 0 and C m C_m C m in the clique graph Γ ( G ) \Gamma(G) Γ ( G ) . For i = 1 , 2 , … , m i=1,2,\ldots,m i = 1 , 2 , … , m take a vertex x i ∈ C i − 1 ∩ C i x_i\in C_{i-1}\cap C_i x i ∈ C i − 1 ∩ C i . Then x 1 ∼ x 2 ∼ ⋯ ∼ x m x_1\sim x_2\sim\cdots\sim x_m x 1 ∼ x 2 ∼ ⋯ ∼ x m is a shortest path in G G G connecting x 1 x_1 x 1 and x m x_m x m .
The proofs of the above assertions require only elementary combinatorial arguments directly from the definition and are therefore omitted, for relevant results see [12 ] , and for more on clique graphs see [14 , 16 , 39 , 43 ] .
Block Graphs
A connected graph G = ( V , E ) G=(V,E) G = ( V , E ) is called a block graph if every 2-connected component is a clique. The singleton graph K 1 K_1 K 1 is a block graph by definition. Any tree is a block graph, where any 2-connected component is an edge and vice versa.
Lemma 3.9. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 . Then a subset W ⊂ V W\subset V W ⊂ V is a maximal clique if and only if ⟨ W ⟩ \langle W\rangle ⟨ W ⟩ is a 2-connected component.
Proof. Suppose first that ⟨ W ⟩ \langle W\rangle ⟨ W ⟩ is a 2-connected component. By definition of a block graph, W W W is a clique. Let W 1 W_1 W 1 be a clique of G G G such that W ⊂ W 1 W\subset W_1 W ⊂ W 1 . Since ⟨ W ⟩ \langle W\rangle ⟨ W ⟩ is a 2-connected graph, we have ∣ W ∣ ≥ 2 |W|\ge2 ∣ W ∣ ≥ 2 . Then ⟨ W 1 ⟩ \langle W_1\rangle ⟨ W 1 ⟩ is a finite or infinite complete graph on ∣ W 1 ∣ ≥ 2 |W_1|\ge2 ∣ W 1 ∣ ≥ 2 vertices, and hence is 2-connected. Since ⟨ W ⟩ \langle W\rangle ⟨ W ⟩ is a maximal 2-connected subgraph, we come to W = W 1 W=W_1 W = W 1 , which means that W W W is a maximal clique. :: Conversely, let W ⊂ V W \subset V W ⊂ V be a maximal clique. Since V V V contains no isolated vertices by ∣ V ∣ ≥ 2 |V| \ge2 ∣ V ∣ ≥ 2 , ⟨ W ⟩ \langle W\rangle ⟨ W ⟩ is a finite or infinite complete graph on ∣ W ∣ ≥ 2 |W| \ge2 ∣ W ∣ ≥ 2 vertices and is therefore 2-connected. By Lemma 3.2 there exists a 2-connected component H 1 = ( W 1 , F 1 ) H_1=(W_1,F_1) H 1 = ( W 1 , F 1 ) containing ⟨ W ⟩ \langle W\rangle ⟨ W ⟩ , that is, W ⊂ W 1 W \subset W_1 W ⊂ W 1 . Note that W 1 W_1 W 1 is a clique by definition of a block graph. Since W W W is a maximal clique, we conclude that W = W 1 W=W_1 W = W 1 and ⟨ W ⟩ \langle W\rangle ⟨ W ⟩ is a 2-connected component.
Lemma 3.10. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph. Then for any distinct maximal cliques C 1 C_1 C 1 and C 2 C_2 C 2 we have ∣ C 1 ∩ C 2 ∣ ≤ 1 |C_1 \cap C_2| \le1 ∣ C 1 ∩ C 2 ∣ ≤ 1 .
Proof. Immediate from Lemmas 3.3 and 3.9.
Proposition 3.12. Any block graph is geodetic, i.e., every pair of vertices is connected by a unique shortest path (called a geodesic).
Proof. The proof can be given by an elementary argument based on the definition. For example, it can be proved by induction on n ≥ 1 n \ge1 n ≥ 1 that any pair of vertices x , y x,y x , y with d ( x , y ) = n d(x,y)=n d ( x , y ) = n admits a unique shortest path.
The result stated in Proposition 3.12 is well-known and can be found, for example, in [6 , 11 ] . However, their main purpose was to obtain an interesting characterization of the block graphs using the Wiener and Szeged indices.
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. The clique degree of a vertex x ∈ V x \in V x ∈ V is defined to be the number of maximal cliques containing x x x , and is denoted by cd ( x ) \operatorname{cd}(x) cd ( x ) . Obviously, cd ( x ) ≥ 1 \operatorname{cd}(x) \ge1 cd ( x ) ≥ 1 for any x ∈ V x \in V x ∈ V . If there are infinitely many maximal cliques containing x x x , we simply write cd ( x ) = ∞ \operatorname{cd}(x)=\infty cd ( x ) = ∞ . The clique degree is useful for the structure of block graphs.
Cactus-like Graphs
Although the concept of a cactus-like graph introduced in [5 ] is limited to finite graphs, the definition applies equally well to infinite graphs without modification. A graph G = ( V , E ) G=(V,E) G = ( V , E ) is called cactus-like if the clique graph Γ ( G ) \Gamma(G) Γ ( G ) is a tree and ∣ C 1 ∩ C 2 ∣ ≤ 1 |C_1 \cap C_2| \le1 ∣ C 1 ∩ C 2 ∣ ≤ 1 for any pair of distinct maximal cliques C 1 C_1 C 1 and C 2 C_2 C 2 of G G G . Any cactus-like graph is connected by Lemma 3.6. By definition, the complete graph K n K_n K n with n ≥ 1 n \ge1 n ≥ 1 as well as infinite complete graphs K ∞ K_\infty K ∞ is cactus-like.
Proposition 3.13. Any cactus-like graph is a block graph.
Proof. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a cactus-like graph and H = ( W , F ) H=(W,F) H = ( W , F ) any 2-connected component of G G G . Since H H H is an induced subgraph, the adjacency relation in H H H coincides with that in G G G . We need to show that W W W is a clique. If ∣ W ∣ = 2 |W|=2 ∣ W ∣ = 2 , then H ≅ K 2 H \cong K_2 H ≅ K 2 and hence W W W is certainly a clique. Hereafter we assume that ∣ W ∣ ≥ 3 |W| \ge3 ∣ W ∣ ≥ 3 . It is sufficient to prove that every pair of distinct vertices in W W W is adjacent. We prove this by contradiction.
Suppose that H = ( W , F ) H=(W,F) H = ( W , F ) is a 2-connected component of G G G with ∣ W ∣ ≥ 3 |W| \ge3 ∣ W ∣ ≥ 3 that is not a clique. Then there exists an induced path of length 2 in H H H , say,
a ∼ c ∼ b , (7) a \sim c \sim b, \tag*{(7)} a ∼ c ∼ b , (7)
where a , b , c ∈ W a,b,c \in W a , b , c ∈ W are mutually distinct and a ≁ b a \not\sim b a ∼ b . Let C 1 C_1 C 1 and C 2 C_2 C 2 be maximal cliques of G G G containing { a , c } \{a,c\} { a , c } and { c , b } \{c,b\} { c , b } , respectively. Such maximal cliques exist by Lemma 3.5 . Since (7) becomes a shortest path connecting a a a and b b b in G G G , by Lemma 3.7 we see that
C 1 ∼ C 2 (8) C_1 \sim C_2 \tag*{(8)} C 1 ∼ C 2 (8)
is a shortest path, in particular, C 1 ≠ C 2 C_1 \ne C_2 C 1 = C 2 and C 1 ∩ C 2 = { c } C_1 \cap C_2 = \{c\} C 1 ∩ C 2 = { c } . Since H ∖ { c } H \setminus\{c\} H ∖ { c } is connected because H H H is 2-connected, we may take a shortest path connecting a a a and b b b in H ∖ { c } H \setminus\{c\} H ∖ { c } , say,
a = x 0 ∼ x 1 ∼ ⋯ ∼ x s − 1 ∼ x s = b , x i ∈ W ∖ { c } , s ≥ 2. (9) a=x_0 \sim x_1 \sim\cdots\sim x_{s-1} \sim x_s=b,\qquad x_i \in W \setminus\{c\},\quad s \ge2. \tag*{(9)} a = x 0 ∼ x 1 ∼ ⋯ ∼ x s − 1 ∼ x s = b , x i ∈ W ∖ { c } , s ≥ 2. (9)
For i = 1 , 2 , … , s i=1,2,\ldots,s i = 1 , 2 , … , s let D i D_i D i be a maximal clique containing { x i − 1 , x i } \{x_{i-1},x_i\} { x i − 1 , x i } . It is easy to see that
D 1 ∼ D 2 ∼ ⋯ ∼ D s (10) D_1 \sim D_2 \sim\cdots\sim D_s \tag*{(10)} D 1 ∼ D 2 ∼ ⋯ ∼ D s (10)
and these are mutually distinct. In fact, if D i = D j D_i=D_j D i = D j happens for $1 \le i < j \le s$, we have { x i − 1 , x j } ⊂ D i = D j \{x_{i-1},x_j\} \subset D_i=D_j { x i − 1 , x j } ⊂ D i = D j and x i − 1 ∼ x j x_{i-1} \sim x_j x i − 1 ∼ x j . This contradicts that (9) is a shortest path connecting a a a and b b b in H ∖ { c } H \setminus\{c\} H ∖ { c } .
In view of a ∈ C 1 ∩ D 1 a \in C_1 \cap D_1 a ∈ C 1 ∩ D 1 and b ∈ C 2 ∩ D s b \in C_2 \cap D_s b ∈ C 2 ∩ D s there are three cases:
(Case 1) C 1 = D 1 C_1=D_1 C 1 = D 1 and C 2 = D s C_2=D_s C 2 = D s . Note first that s ≥ 3 s \ge3 s ≥ 3 . In fact, if s = 2 s=2 s = 2 we have { c , x 1 } ⊂ C 1 = D 1 \{c,x_1\} \subset C_1=D_1 { c , x 1 } ⊂ C 1 = D 1 and { c , x 1 } ⊂ C 2 = D 2 \{c,x_1\} \subset C_2=D_2 { c , x 1 } ⊂ C 2 = D 2 . Then we come to ∣ C 1 ∩ C 2 ∣ ≥ 2 |C_1 \cap C_2| \ge2 ∣ C 1 ∩ C 2 ∣ ≥ 2 , which contradicts that G G G is cactus-like. Concatenating the two paths in (8) and (10) , we obtain a cycle in Γ ( G ) \Gamma(G) Γ ( G ) of length s ≥ 3 s \ge3 s ≥ 3 . But this contradicts that Γ ( G ) \Gamma(G) Γ ( G ) is a tree.
(Case 2) C 1 ∼ D 1 C_1 \sim D_1 C 1 ∼ D 1 and C 2 = D s C_2=D_s C 2 = D s . We note that D i ≠ C 1 D_i \ne C_1 D i = C 1 for 2 ≤ i ≤ s 2 \le i \le s 2 ≤ i ≤ s . In fact, if D i = C 1 D_i=C_1 D i = C 1 occurs, we have { x 0 , x i } ⊂ D i = C 1 \{x_0,x_i\} \subset D_i=C_1 { x 0 , x i } ⊂ D i = C 1 and hence x 0 ∼ x i x_0 \sim x_i x 0 ∼ x i . This contradicts that (9) is a shortest path connecting a a a and b b b in H ∖ { c } H \setminus\{c\} H ∖ { c } . Thus, we come to
C 1 ∼ D 1 ∼ D 2 ∼ ⋯ ∼ D s = C 2 C_1 \sim D_1 \sim D_2 \sim\cdots\sim D_s=C_2 C 1 ∼ D 1 ∼ D 2 ∼ ⋯ ∼ D s = C 2
and these are mutually distinct. Then combining (8) , we obtain a cycle of length s + 1 ≥ 3 s+1 \ge3 s + 1 ≥ 3 in Γ ( G ) \Gamma(G) Γ ( G ) . But this contradicts that Γ ( G ) \Gamma(G) Γ ( G ) is a tree. Similarly, the case where C 1 = D 1 C_1=D_1 C 1 = D 1 and C 2 ∼ D s C_2 \sim D_s C 2 ∼ D s leads to a contradiction.
(Case 3) C 1 ∼ D 1 C_1 \sim D_1 C 1 ∼ D 1 and C 2 ∼ D s C_2 \sim D_s C 2 ∼ D s . In a similar argument as in (Case 2) we obtain a cycle of length s + 2 ≥ 4 s+2 \ge4 s + 2 ≥ 4 in Γ ( G ) \Gamma(G) Γ ( G ) , which is a contradiction.
Consequently, in any case we come to a contradiction and the proof is complete.
We are in a good position to collect the equivalent conditions for a graph to be cactus-like. In particular, the equivalence of two conditions (i) ⇔ \Leftrightarrow ⇔ (ii) in the main Theorem 1.2 is established.
Proposition 3.14. For a graph G = ( V , E ) G=(V,E) G = ( V , E ) the following conditions are equivalent:
(i) G G G is cactus-like, that is, every pair of distinct maximal cliques has at most one vertex in common and the clique graph Γ ( G ) \Gamma(G) Γ ( G ) is a tree;
(ii) G G G is a block graph and Γ ( G ) \Gamma(G) Γ ( G ) is a tree.
(iii) G G G is a block graph and cd ( x ) ≤ 2 \operatorname{cd}(x)\le2 cd ( x ) ≤ 2 for all x ∈ V x\in V x ∈ V .
Proof. (i) ⇒ \Rightarrow ⇒ (ii) is obvious by Proposition 3.13, and (ii) ⇒ \Rightarrow ⇒ (i) by Lemma 3.10.
(ii) ⇒ \Rightarrow ⇒ (iii). Suppose that cd ( x ) ≥ 3 \operatorname{cd}(x)\ge3 cd ( x ) ≥ 3 for some x ∈ V x\in V x ∈ V . Then there exist distinct maximal cliques C 1 C_1 C 1 , C 2 C_2 C 2 and C 3 C_3 C 3 containing x x x . Since C 1 ∩ C 2 ∩ C 3 ≠ ∅ C_1\cap C_2\cap C_3\ne\varnothing C 1 ∩ C 2 ∩ C 3 = ∅ , we see that C 1 ∼ C 2 ∼ C 3 ∼ C 1 C_1\sim C_2\sim C_3\sim C_1 C 1 ∼ C 2 ∼ C 3 ∼ C 1 form a cycle of length 3 in Γ ( G ) \Gamma(G) Γ ( G ) . This contradicts that Γ ( G ) \Gamma(G) Γ ( G ) is a tree.
(iii) ⇒ \Rightarrow ⇒ (ii). Suppose that Γ ( G ) \Gamma(G) Γ ( G ) is not a tree. Then there exists a cycle in Γ ( G ) \Gamma(G) Γ ( G ) , say,
C 1 ∼ C 2 ∼ ⋯ ∼ C s ∼ C 1 , C_1\sim C_2\sim\cdots\sim C_s\sim C_1, C 1 ∼ C 2 ∼ ⋯ ∼ C s ∼ C 1 ,
where s ≥ 3 s\ge3 s ≥ 3 and C 1 , C 2 , … , C s C_1,C_2,\ldots,C_s C 1 , C 2 , … , C s are mutually distinct. For i = 1 , 2 , … , s i=1,2,\ldots,s i = 1 , 2 , … , s we choose x i ∈ V x_i\in V x i ∈ V such that C i ∩ C i + 1 = { x i } C_i\cap C_{i+1}=\{x_i\} C i ∩ C i + 1 = { x i } , where we understand C s + 1 = C 1 C_{s+1}=C_1 C s + 1 = C 1 . We note that x 1 , x 2 , … , x s x_1,x_2,\ldots,x_s x 1 , x 2 , … , x s are mutually distinct. In fact, if x i = x j x_i=x_j x i = x j for some 1 ≤ i < j ≤ s 1\le i<j\le s 1 ≤ i < j ≤ s , we see that x i = x j ∈ C i ∩ C i + 1 ∩ C j + 1 x_i=x_j\in C_i\cap C_{i+1}\cap C_{j+1} x i = x j ∈ C i ∩ C i + 1 ∩ C j + 1 and cd ( x i ) ≥ 3 \operatorname{cd}(x_i)\ge3 cd ( x i ) ≥ 3 . This contradicts the assumption of (iii). Thus,
x 1 ∼ x 2 ∼ ⋯ ∼ x s ∼ x 1 , x_1\sim x_2\sim\cdots\sim x_s\sim x_1, x 1 ∼ x 2 ∼ ⋯ ∼ x s ∼ x 1 ,
becomes a cycle in G G G of length s s s . We then see that C 1 ∪ C 2 ∪ ⋯ ∪ C s C_1\cup C_2\cup\cdots\cup C_s C 1 ∪ C 2 ∪ ⋯ ∪ C s is a 2-connected subgraph. Hence it is contained in a 2-connected component H H H , which is a maximal clique by Lemma 3.9. This contradicts that C 1 , … , C s C_1,\ldots,C_s C 1 , … , C s are distinct maximal cliques. □ \square □
Remark 3.15. As an extremal case of condition (iii) in Proposition 3.14, we note that a block graph G = ( V , E ) G=(V,E) G = ( V , E ) is reduced to a finite or infinite complete graph if cd ( x ) = 1 \operatorname{cd}(x)=1 cd ( x ) = 1 for all x ∈ V x\in V x ∈ V .
QEC of Block Graphs
Upper Bound for QEC of Block Graphs
We first present the key result required for our characterization of cactus-like graphs. The proof will be given in the next section.
Theorem 4.1. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph and assume that
p = sup { cd ( x ) ; x ∈ V } < ∞ . p=\sup\{\operatorname{cd}(x);x\in V\}<\infty. p = sup { cd ( x ) ; x ∈ V } < ∞. Define a matrix Ψ = [ ψ ( x , y ) ] x , y ∈ V \Psi=[\psi(x,y)]_{x,y\in V} Ψ = [ ψ ( x , y ) ] x , y ∈ V by
Ψ = D − 1 p ( J − I ) . (11) \Psi=D-\frac{1}{p}(J-I). \tag*{(11)} Ψ = D − p 1 ( J − I ) . (11)
where D = [ d ( x , y ) ] D=[d(x,y)] D = [ d ( x , y )] is the distance matrix of G G G , J J J the all-one matrix, and I I I the identity matrix. Or equivalently,
ψ ( x , y ) = { 0 , if x = y , d ( x , y ) − 1 p , if x ≠ y , x , y ∈ V . (12) \psi(x,y)=
\begin{cases}
0, & \text{if } x=y,\\
d(x,y)-\frac{1}{p}, & \text{if } x\ne y,
\end{cases}
\qquad x,y\in V. \tag*{(12)} ψ ( x , y ) = { 0 , d ( x , y ) − p 1 , if x = y , if x = y , x , y ∈ V . (12)
Then Ψ \Psi Ψ is conditionally negative definite.
The matrix Ψ \Psi Ψ defined by (11) plays a crucial role in achieving our goal. It is noteworthy that Ψ \Psi Ψ has zeroes on the diagonal and the off-diagonal entries are the distances shifted downwards by 1 / p 1/p 1/ p . As an immediate consequence of Theorem 4.1, we derive an upper bound for QEC ( G ) \operatorname{QEC}(G) QEC ( G ) for a block graph G G G .
Theorem 4.2. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 and assume that
p = sup { cd ( x ) ; x ∈ V } < ∞ . p=\sup\{\operatorname{cd}(x);x\in V\}<\infty. p = sup { cd ( x ) ; x ∈ V } < ∞. Then
QEC ( G ) ≤ − 1 p . (13) \operatorname{QEC}(G)\le-\frac{1}{p}. \tag*{(13)} QEC ( G ) ≤ − p 1 . (13) In particular, for any cactus-like graph G G G we have p ≤ 2 p\le2 p ≤ 2 and
QEC ( G ) ≤ − 1 2 . (14) \operatorname{QEC}(G)\le-\frac{1}{2}. \tag*{(14)} QEC ( G ) ≤ − 2 1 . (14)
Proof. Take an arbitrary f ∈ C 0 ( V ) f\in C_0(V) f ∈ C 0 ( V ) satisfying ⟨ 1 , f ⟩ = 0 \langle1,f\rangle=0 ⟨ 1 , f ⟩ = 0 and ⟨ f , f ⟩ = 1 \langle f,f\rangle=1 ⟨ f , f ⟩ = 1 . Using the matrix Ψ \Psi Ψ introduced in Theorem 4.1, we come to
⟨ f , D f ⟩ = ⟨ f , Ψ f ⟩ + 1 p ⟨ f , ( J − I ) f ⟩ = ⟨ f , Ψ f ⟩ + 1 p ( ⟨ 1 , f ⟩ 2 − ⟨ f , f ⟩ ) = ⟨ f , Ψ f ⟩ − 1 p . \begin{aligned}
\langle f,Df\rangle=\langle f,\Psi f\rangle+\frac{1}{p}\langle f,(J-I)f\rangle\\
&=\langle f,\Psi f\rangle+\frac{1}{p}\left(\langle1,f\rangle^2-\langle f,f\rangle\right) \\
&=\langle f,\Psi f\rangle-\frac{1}{p}.
\end{aligned} ⟨ f , D f ⟩ = ⟨ f , Ψ f ⟩ + p 1 ⟨ f , ( J − I ) f ⟩ = ⟨ f , Ψ f ⟩ + p 1 ( ⟨ 1 , f ⟩ 2 − ⟨ f , f ⟩ ) = ⟨ f , Ψ f ⟩ − p 1 .
Moreover, since ⟨ f , Ψ f ⟩ ≤ 0 \langle f,\Psi f\rangle\le0 ⟨ f , Ψ f ⟩ ≤ 0 by Theorem 4.1, we obtain
⟨ f , D f ⟩ = ⟨ f , Ψ f ⟩ − 1 p ≤ − 1 p , \langle f,Df\rangle=\langle f,\Psi f\rangle-\frac{1}{p}\le-\frac{1}{p}, ⟨ f , D f ⟩ = ⟨ f , Ψ f ⟩ − p 1 ≤ − p 1 ,
from which (4.3) follows. For a cactus-like graph G G G , we need only to note that cd ( x ) ≤ 2 \operatorname{cd}(x)\le2 cd ( x ) ≤ 2 for all x ∈ V x\in V x ∈ V , see Proposition 3.14.
Upper Bound for QEC of Finite Block Graphs
We will obtain a refinement of Theorem 4.2 for finite block graphs and complete the characterization of finite cactus-like graphs in terms of QEC \operatorname{QEC} QEC . We begin with the elementary fact that any finite block graph with at least two maximal cliques contains an ‘end maximal clique.’
Lemma 4.3. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a finite block graph and C \mathcal{C} C the set of maximal cliques of G G G . If ∣ C ∣ ≥ 2 |\mathcal{C}|\ge2 ∣ C ∣ ≥ 2 , there exists C ∈ C C\in\mathcal{C} C ∈ C such that
∣ ⋃ D ∈ C ∖ { C } D ∩ C ∣ = 1. (15) \left|\bigcup_{D\in\mathcal{C}\setminus\{C\}}D\cap C\right|=1. \tag*{(15)} D ∈ C ∖ { C } ⋃ D ∩ C = 1. (15) (In this case C C C is called an end maximal clique.)
Proof. Since the clique graph Γ ( G ) \Gamma(G) Γ ( G ) is connected and ∣ C ∣ ≥ 2 |\mathcal{C}|\ge2 ∣ C ∣ ≥ 2 by assumption, we see that for every C ∈ C C\in\mathcal{C} C ∈ C there exists D ∈ C D\in\mathcal{C} D ∈ C such that D ∼ C D\sim C D ∼ C , that is ∣ D ∩ C ∣ = 1 |D\cap C|=1 ∣ D ∩ C ∣ = 1 . Therefore, the left-hand side of (4.5) is at least one. To prove the assertion by contradiction we suppose that every C ∈ C C\in\mathcal{C} C ∈ C satisfies
∣ ⋃ D ∈ C ∖ { C } D ∩ C ∣ ≥ 2. (16) \left|\bigcup_{D\in\mathcal{C}\setminus\{C\}}D\cap C\right|\ge2. \tag*{(16)} D ∈ C ∖ { C } ⋃ D ∩ C ≥ 2. (16)
Since ∣ C ∩ D ∣ ≤ 1 |C\cap D|\le1 ∣ C ∩ D ∣ ≤ 1 for any D ∈ C ∖ { C } D\in\mathcal{C}\setminus\{C\} D ∈ C ∖ { C } , (4.6) means that there exist D 1 , D 2 ∈ C ∖ { C } D_1,D_2\in\mathcal{C}\setminus\{C\} D 1 , D 2 ∈ C ∖ { C } such that D 1 ≠ D 2 D_1\ne D_2 D 1 = D 2 , D 1 ∼ C ∼ D 2 D_1\sim C\sim D_2 D 1 ∼ C ∼ D 2 and D 1 ∩ C ≠ D 2 ∩ C D_1\cap C\ne D_2\cap C D 1 ∩ C = D 2 ∩ C . Based on this we construct a walk in Γ ( G ) \Gamma(G) Γ ( G ) :
C 1 ∼ C 2 ∼ C 3 ∼ ⋯ ∼ C s ∼ ⋯ , (17) C_1\sim C_2\sim C_3\sim\cdots\sim C_s\sim\cdots, \tag*{(17)} C 1 ∼ C 2 ∼ C 3 ∼ ⋯ ∼ C s ∼ ⋯ , (17)
satisfying
C s − 1 ≠ C s + 1 , C s − 1 ∩ C s ≠ C s ∩ C s + 1 , s = 2 , 3 , … . C_{s-1}\ne C_{s+1},\qquad C_{s-1}\cap C_s\ne C_s\cap C_{s+1},\qquad s=2,3,\ldots. C s − 1 = C s + 1 , C s − 1 ∩ C s = C s ∩ C s + 1 , s = 2 , 3 , … .
In fact, we choose C 1 C_1 C 1 and C 2 C_2 C 2 in such a way that C 1 ∼ C 2 C_1\sim C_2 C 1 ∼ C 2 , and applying the aforementioned property we may find C 3 C_3 C 3 satisfying the desired condition. Then we repeat this process. However, since G G G is a finite graph, C \mathcal{C} C is finite as a subset of the power set 2 V 2^V 2 V . Therefore, in (4.7) we may find s ≥ 4 s\ge4 s ≥ 4 such that C 1 , C 2 , … , C s − 1 C_1,C_2,\ldots,C_{s-1} C 1 , C 2 , … , C s − 1 are mutually distinct and C s = C t C_s=C_t C s = C t for some 1 ≤ t ≤ s − 3 1\le t\le s-3 1 ≤ t ≤ s − 3 . Namely, we come to a cycle
C t ∼ C t + 1 ∼ ⋯ ∼ C s − 1 ∼ C s = C t C_t\sim C_{t+1}\sim\cdots\sim C_{s-1}\sim C_s=C_t C t ∼ C t + 1 ∼ ⋯ ∼ C s − 1 ∼ C s = C t
of length s − t ≥ 3 s-t\ge3 s − t ≥ 3 . Then ⟨ C t ∪ C t + 1 ∪ ⋯ ∪ C s − 1 ⟩ \langle C_t\cup C_{t+1}\cup\cdots\cup C_{s-1}\rangle ⟨ C t ∪ C t + 1 ∪ ⋯ ∪ C s − 1 ⟩ becomes a 2-connected subgraph of G G G and hence is contained in a 2-connected component. But this 2-connected component is a clique as G G G is a block graph. Thus the mutually distinct maximal cliques C t , C t + 1 , … , C s − 1 C_t,C_{t+1},\ldots,C_{s-1} C t , C t + 1 , … , C s − 1 are contained in another maximal clique, which is a contradiction. □ \square □
Theorem 4.4. Let G G G be a finite block graph with two or more maximal cliques. Then we have
QEC ( G ) < − 1 p , p = max { cd ( x ) ; x ∈ V } . (18) \operatorname{QEC}(G)<-\frac{1}{p},\qquad p=\max\{\operatorname{cd}(x);x\in V\}. \tag*{(18)} QEC ( G ) < − p 1 , p = max { cd ( x ) ; x ∈ V } . (18) Proof. Let C \mathcal{C} C be the set of maximal cliques of G G G . By assumption we have ∣ C ∣ ≥ 2 |\mathcal{C}|\ge2 ∣ C ∣ ≥ 2 . We prove (4.8) by induction on the number s = ∣ C ∣ s=|\mathcal{C}| s = ∣ C ∣ . For s = 2 s=2 s = 2 we have G = K m ⋆ K n G=K_m\star K_n G = K m ⋆ K n for some m , n ≥ 2 m,n\ge2 m , n ≥ 2 and p = 2 p=2 p = 2 . Since
QEC ( K m ⋆ K n ) = − 1 1 + ( 1 − 1 m ) ( 1 − 1 n ) < − 1 2 , \operatorname{QEC}(K_m\star K_n)=-\frac{1}{1+\sqrt{\left(1-\frac{1}{m}\right)\left(1-\frac{1}{n}\right)}}<-\frac{1}{2}, QEC ( K m ⋆ K n ) = − 1 + ( 1 − m 1 ) ( 1 − n 1 ) 1 < − 2 1 ,
see Theorem A.3 in Appendix, the assertion (18) certainly holds for s = 2 s=2 s = 2 . Let s ≥ 3 s\ge3 s ≥ 3 and assume that (18) holds up to s − 1 s-1 s − 1 . We need to show that (18) holds for any finite block graph G = ( V , E ) G=(V,E) G = ( V , E ) with s s s maximal cliques. We proceed by contradiction.
Suppose, for the sake of contradiction, that there exists a finite block graph G G G with s s s maximal cliques for which (18) fails. In light of Theorem 4.2 we have
QEC ( G ) = − 1 p . (19) \operatorname{QEC}(G)=-\frac{1}{p}. \tag*{(19)} QEC ( G ) = − p 1 . (19)
We note that p = max { cd ( x ) ; x ∈ V } ≥ 2 p=\max\{\operatorname{cd}(x);x\in V\}\ge2 p = max { cd ( x ) ; x ∈ V } ≥ 2 . By Lemma 4.3 there exists an end maximal clique W W W of G G G . Let a ∈ W a\in W a ∈ W be a unique vertex such that W ∩ W 1 = { a } W\cap W_1=\{a\} W ∩ W 1 = { a } for any W 1 ∼ W W_1\sim W W 1 ∼ W . Set V ′ = V ∖ ( W ∖ { a } ) V'=V\setminus(W\setminus\{a\}) V ′ = V ∖ ( W ∖ { a }) . Then G ′ = ⟨ V ′ ⟩ = G ∖ ( W ∖ { a } ) G'=\langle V'\rangle=G\setminus(W\setminus\{a\}) G ′ = ⟨ V ′ ⟩ = G ∖ ( W ∖ { a }) becomes a block graph with s − 1 s-1 s − 1 maximal cliques. By the induction hypothesis we have
QEC ( G ′ ) < − 1 p . (20) \operatorname{QEC}(G')<-\frac{1}{p}. \tag*{(20)} QEC ( G ′ ) < − p 1 . (20)
On the other hand, by (19) we may choose f ∈ C ( V ) f\in C(V) f ∈ C ( V ) such that
⟨ f , D f ⟩ = − 1 p , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0. (21) \langle f,Df\rangle=-\frac{1}{p},\qquad\langle f,f\rangle=1,\qquad\langle\mathbf{1},f\rangle=0. \tag*{(21)} ⟨ f , D f ⟩ = − p 1 , ⟨ f , f ⟩ = 1 , ⟨ 1 , f ⟩ = 0. (21)
Assume that f ( x ) = 0 f(x)=0 f ( x ) = 0 for any x ∈ W ∖ { a } x\in W\setminus\{a\} x ∈ W ∖ { a } . Then f f f is regarded as a function in C ( V ′ ) C(V') C ( V ′ ) . Since G ′ G' G ′ is isometrically embedded in G G G , the distance matrix of G ′ G' G ′ coincides with D ↾ V ′ D\mathord{\upharpoonright}_{V'} D ↾ V ′ . Then (21) implies that QEC ( G ′ ) ≥ − 1 / p \operatorname{QEC}(G')\ge-1/p QEC ( G ′ ) ≥ − 1/ p , which contradicts (20) . Therefore, there exists some x 0 ∈ W ∖ { a } x_0\in W\setminus\{a\} x 0 ∈ W ∖ { a } such that f ( x 0 ) ≠ 0 f(x_0)\ne0 f ( x 0 ) = 0 .
Taking k ≥ 2 k\ge2 k ≥ 2 we consider the star product G ~ = ( G , x 0 ) ⋆ K k \widetilde{G}=(G,x_0)\star K_k G = ( G , x 0 ) ⋆ K k . With the help of Proposition 2.5 and (19) we come to
− 1 p = QEC ( G ) < QEC ( G ~ ) . (22) -\frac{1}{p}=\operatorname{QEC}(G)<\operatorname{QEC}(\widetilde{G}). \tag*{(22)} − p 1 = QEC ( G ) < QEC ( G ) . (22)
On the other hand, since G ~ = ( V ~ , E ~ ) \widetilde{G}=(\widetilde{V},\widetilde{E}) G = ( V , E ) is a block graph satisfying p = max { cd ( x ) ; x ∈ V ~ } p=\max\{\operatorname{cd}(x);x\in\widetilde{V}\} p = max { cd ( x ) ; x ∈ V } , by Theorem 4.2 we have
QEC ( G ~ ) ≤ − 1 p . (23) \operatorname{QEC}(\widetilde{G})\le-\frac{1}{p}. \tag*{(23)} QEC ( G ) ≤ − p 1 . (23)
Since (22) and (23) are incompatible, we conclude that (18) holds for any finite block graph G G G with s s s maximal cliques. □ \square □
Remark 4.5. If G G G is a finite block graph with just one maximal clique, it is a complete graph K n K_n K n with n ≥ 2 n\ge2 n ≥ 2 . Then we have p = 1 p=1 p = 1 and QEC ( G ) = − 1 \operatorname{QEC}(G)=-1 QEC ( G ) = − 1 so that (18) fails.
Remark 4.6. It is plausible that Theorem 4.4 remains valid for a block graph which is not necessarily finite but has finitely many maximal cliques. The detailed study will appear elsewhere.
Characterization of Cactus-like Graphs
The main result (Theorem 1.2 ) of this paper is restated in the following
Theorem 4.7. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a finite connected graph with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 . Then the following conditions are equivalent:
(i) G G G is cactus-like, that is, every pair of distinct maximal cliques has at most one vertex in common and the clique graph Γ ( G ) \Gamma(G) Γ ( G ) is a tree;
(ii) G G G is a block graph whose clique graph Γ ( G ) \Gamma(G) Γ ( G ) is a tree;
(iii) QEC ( G ) < − 1 / 2 \operatorname{QEC}(G)<-1/2 QEC ( G ) < − 1/2 .
Proof. The equivalence (i) ⇔ \Leftrightarrow ⇔ (ii) is already shown in Proposition 3.14 . As is mentioned in Introduction the implication (iii) ⇒ \Rightarrow ⇒ (i) was proved in [5 ] . Here we prove the implication (i) ⇒ \Rightarrow ⇒ (iii). Let G = ( V , E ) G=(V,E) G = ( V , E ) be a cactus-like graph. By Proposition 3.14 we have p = max { cd ( x ) ; x ∈ V } ≤ 2 p=\max\{\operatorname{cd}(x);x\in V\}\le2 p = max { cd ( x ) ; x ∈ V } ≤ 2 . If p = 2 p=2 p = 2 , applying Theorem 4.4 , we obtain QEC ( G ) < − 1 / 2 \operatorname{QEC}(G)<-1/2 QEC ( G ) < − 1/2 . If p = 1 p=1 p = 1 , then G G G is a complete graph and QEC ( G ) = − 1 < − 1 / 2 \operatorname{QEC}(G)=-1<-1/2 QEC ( G ) = − 1 < − 1/2 , see Remark 4.5. □ \square □
Lower Bound for QEC of Block Graphs
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 . Consider a vertex x ∈ V x\in V x ∈ V and assume that q = cd ( x ) < ∞ q=\operatorname{cd}(x)<\infty q = cd ( x ) < ∞ . Let C 1 , … , C q C_1,\ldots,C_q C 1 , … , C q be the maximal cliques containing x x x . We see easily that
⟨ C 1 , C 2 , … , C q ⟩ ≅ K ∣ C 1 ∣ ⋆ K ∣ C 2 ∣ ⋆ ⋯ ⋆ K ∣ C q ∣ , \langle C_1,C_2,\ldots,C_q\rangle\cong K_{\lvert C_1\rvert}\star K_{\lvert C_2\rvert}\star\cdots\star K_{\lvert C_q\rvert}, ⟨ C 1 , C 2 , … , C q ⟩ ≅ K ∣ C 1 ∣ ⋆ K ∣ C 2 ∣ ⋆ ⋯ ⋆ K ∣ C q ∣ ,
which is an isometric subgraph of G G G . Hence we have
QEC ( G ) ≥ QEC ( K ∣ C 1 ∣ ⋆ K ∣ C 2 ∣ ⋆ ⋯ ⋆ K ∣ C q ∣ ) . (24) \operatorname{QEC}(G)\ge\operatorname{QEC}(K_{\lvert C_1\rvert}\star K_{\lvert C_2\rvert}\star\cdots\star K_{\lvert C_q\rvert}). \tag*{(24)} QEC ( G ) ≥ QEC ( K ∣ C 1 ∣ ⋆ K ∣ C 2 ∣ ⋆ ⋯ ⋆ K ∣ C q ∣ ) . (24)
The exact value of the right-hand side is described only implicitly except some special cases, see Theorem A.3 in Appendix. Nevertheless, if we take the supremum of the right-hand side over x ∈ V x\in V x ∈ V , we may obtain a better lower bound of QEC ( G ) \operatorname{QEC}(G) QEC ( G ) . Here we derive a simple lower bound for QEC ( G ) \operatorname{QEC}(G) QEC ( G ) from (4.14).
Proposition 4.8. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 and x ∈ V x\in V x ∈ V . Assume that q = cd ( x ) < ∞ q=\operatorname{cd}(x)<\infty q = cd ( x ) < ∞ and let C 1 , … , C q C_1,\ldots,C_q C 1 , … , C q be the maximal cliques containing x x x . If there exists a finite maximal clique containing x x x , setting n ∗ = min { ∣ C 1 ∣ , ∣ C 2 ∣ , … , ∣ C q ∣ } < ∞ n_*=\min\{\lvert C_1\rvert,\lvert C_2\rvert,\ldots,\lvert C_q\rvert\}<\infty n ∗ = min {∣ C 1 ∣ , ∣ C 2 ∣ , … , ∣ C q ∣} < ∞ , we have
QEC ( G ) ≥ − n ∗ ( n ∗ − 1 ) q + 1 . (25) \operatorname{QEC}(G)\ge-\frac{n_*}{(n_*-1)q+1}. \tag*{(25)} QEC ( G ) ≥ − ( n ∗ − 1 ) q + 1 n ∗ . (25) In particular,
QEC ( G ) ≥ − 2 q + 1 . (26) \operatorname{QEC}(G)\ge-\frac{2}{q+1}. \tag*{(26)} QEC ( G ) ≥ − q + 1 2 . (26)
Proof. Since K ∣ C 1 ∣ ⋆ K ∣ C 2 ∣ ⋆ ⋯ ⋆ K ∣ C q ∣ K_{\lvert C_1\rvert} \star K_{\lvert C_2\rvert} \star\cdots\star K_{\lvert C_q\rvert} K ∣ C 1 ∣ ⋆ K ∣ C 2 ∣ ⋆ ⋯ ⋆ K ∣ C q ∣ contains the q q q -fold star power K n ∗ ⋆ q K_{n_*}^{\star q} K n ∗ ⋆ q as an isometric subgraph, we see from (24) that
QEC ( G ) ≥ QEC ( K n ∗ ⋆ q ) = − n ∗ ( n ∗ − 1 ) q + 1 , \operatorname{QEC}(G) \ge\operatorname{QEC}(K_{n_*}^{\star q}) = -\frac{n_*}{(n_* - 1)q + 1}, QEC ( G ) ≥ QEC ( K n ∗ ⋆ q ) = − ( n ∗ − 1 ) q + 1 n ∗ ,
where the last equality owes to Theorem A.4 in Appendix. Thus, we obtain (4.15). Moreover, (4.16) follows from (4.15) by n ∗ ≥ 2 n_* \ge2 n ∗ ≥ 2 . Alternatively, (4.16) can be verified by observing that a complete bipartite graph K 1 , q K_{1,q} K 1 , q is contained in ⟨ C 1 , C 2 , … , C q ⟩ \langle C_1, C_2, \ldots, C_q\rangle ⟨ C 1 , C 2 , … , C q ⟩ as an isometric subgraph.
Proposition 4.9. Let G = ( V , E ) G = (V, E) G = ( V , E ) be a block graph with ∣ V ∣ ≥ 2 \lvert V\rvert\ge2 ∣ V ∣ ≥ 2 and assume that p = sup { cd ( x ) ; x ∈ V } < ∞ p = \sup\{\operatorname{cd}(x) ; x \in V\} < \infty p = sup { cd ( x ) ; x ∈ V } < ∞ . If there exists a vertex x ∈ V x \in V x ∈ V such that cd ( x ) = p \operatorname{cd}(x) = p cd ( x ) = p and every maximal clique containing x x x is infinite, then we have
QEC ( G ) = − 1 p . (27) \operatorname{QEC}(G) = -\frac{1}{p}. \tag*{(27)} QEC ( G ) = − p 1 . (27)
Proof. For any n ≥ 2 n \ge2 n ≥ 2 , K n ⋆ p K_n^{\star p} K n ⋆ p is contained in K ∞ ⋆ p K_\infty^{\star p} K ∞ ⋆ p as an isometric subgraph. We then see from (24) that
QEC ( G ) ≥ QEC ( K n ⋆ p ) = − n ( n − 1 ) p + 1 , \operatorname{QEC}(G) \ge\operatorname{QEC}(K_n^{\star p}) = -\frac{n}{(n - 1)p + 1}, QEC ( G ) ≥ QEC ( K n ⋆ p ) = − ( n − 1 ) p + 1 n ,
for any n ≥ 2 n \ge2 n ≥ 2 . Letting n → ∞ n \to\infty n → ∞ we obtain
QEC ( G ) ≥ − 1 p . \operatorname{QEC}(G) \ge-\frac{1}{p}. QEC ( G ) ≥ − p 1 .
With the help of Theorem 4.2, we conclude that (4.17) holds.
Proposition 4.10. If a block graph G = ( V , E ) G = (V, E) G = ( V , E ) satisfies sup { cd ( x ) ; x ∈ V } = ∞ \sup\{\operatorname{cd}(x) ; x \in V\} = \infty sup { cd ( x ) ; x ∈ V } = ∞ , we have QEC ( G ) = 0 \operatorname{QEC}(G) = 0 QEC ( G ) = 0 .
Proof. For any p ≥ 1 p \ge1 p ≥ 1 there exists a vertex x ∈ V x \in V x ∈ V such that cd ( x ) ≥ p \operatorname{cd}(x) \ge p cd ( x ) ≥ p . We may take maximal cliques C 1 , … , C p C_1, \ldots, C_p C 1 , … , C p containing x x x . Since ⟨ C 1 , … , C p ⟩ \langle C_1, \ldots, C_p\rangle ⟨ C 1 , … , C p ⟩ contains K 2 ⋆ p ≅ K 1 , p K_2^{\star p} \cong K_{1,p} K 2 ⋆ p ≅ K 1 , p as an isometric subgraph, we have
QEC ( G ) ≥ QEC ( K 2 ⋆ p ) = − 2 p + 1 . \operatorname{QEC}(G) \ge\operatorname{QEC}(K_2^{\star p}) = -\frac{2}{p + 1}. QEC ( G ) ≥ QEC ( K 2 ⋆ p ) = − p + 1 2 .
Letting p → ∞ p \to\infty p → ∞ , we obtain QEC ( G ) ≥ 0 \operatorname{QEC}(G) \ge0 QEC ( G ) ≥ 0 .
On the other hand, Theorem 4.1 remains valid understanding Ψ = D \Psi= D Ψ = D , and so does Theorem 4.2 understanding QEC ( G ) ≤ 0 \operatorname{QEC}(G) \le0 QEC ( G ) ≤ 0 . This is also justified by observing that a block graph is obtained by repeated application of star product of complete graphs. Consequently, QEC ( G ) = 0 \operatorname{QEC}(G) = 0 QEC ( G ) = 0 .
Conditionally Negative Definite Kernels
Preliminaries
Let I I I be an arbitrary non-empty set. Let C ( I ; C ) C(I;\mathbb{C}) C ( I ; C ) be the space of complex-valued functions f : I → C f:I\to\mathbb{C} f : I → C and C 0 ( I ; C ) C_{0}(I;\mathbb{C}) C 0 ( I ; C ) the subspace of those with finite supports. The inner product on C 0 ( I ) C_{0}(I) C 0 ( I ) is defined by
⟨ f , g ⟩ = ∑ i ∈ I f ( i ) ‾ g ( i ) , f , g ∈ C 0 ( I ; C ) . \langle f,g\rangle=\sum_{i\in I}\overline{f(i)}g(i),\qquad f,g\in C_{0}(I;\mathbb{C}). ⟨ f , g ⟩ = i ∈ I ∑ f ( i ) g ( i ) , f , g ∈ C 0 ( I ; C ) .
Let 1 ∈ C ( I ; C ) \mathbf{1}\in C(I;\mathbb{C}) 1 ∈ C ( I ; C ) be the constant function defined by 1 ( i ) = 1 \mathbf{1}(i)=1 1 ( i ) = 1 for all i ∈ I i\in I i ∈ I . Then, we write
⟨ 1 , f ⟩ = ∑ i ∈ I f ( i ) , f ∈ C 0 ( I ; C ) . \langle\mathbf{1},f\rangle=\sum_{i\in I}f(i),\qquad f\in C_{0}(I;\mathbb{C}). ⟨ 1 , f ⟩ = i ∈ I ∑ f ( i ) , f ∈ C 0 ( I ; C ) .
A complex-valued function ψ : I × I → C \psi:I\times I\to\mathbb{C} ψ : I × I → C is called a kernel on I I I . In a natural manner, a function f f f and a kernel ψ \psi ψ on I I I give rise to a column vector f = [ f ( i ) ] f=[f(i)] f = [ f ( i )] and a matrix Ψ = [ ψ ( i , j ) ] \Psi=[\psi(i,j)] Ψ = [ ψ ( i , j )] , respectively. Under this identification we use these notations freely. A kernel ψ \psi ψ on I I I is called hermitian if
ψ ( j , i ) = ψ ( i , j ) ‾ , i , j ∈ I . \psi(j,i)=\overline{\psi(i,j)},\qquad i,j\in I. ψ ( j , i ) = ψ ( i , j ) , i , j ∈ I .
A kernel ψ \psi ψ on I I I is called positive definite if
⟨ f , Ψ f ⟩ = ∑ i , j ∈ I ψ ( i , j ) f ( i ) ‾ f ( j ) ≥ 0 \langle f,\Psi f\rangle=\sum_{i,j\in I}\psi(i,j)\overline{f(i)}f(j)\geq0 ⟨ f , Ψ f ⟩ = i , j ∈ I ∑ ψ ( i , j ) f ( i ) f ( j ) ≥ 0
for any f ∈ C 0 ( I ; C ) f\in C_{0}(I;\mathbb{C}) f ∈ C 0 ( I ; C ) . Recall that a positive definite kernel is necessarily hermitian. A kernel ψ \psi ψ on I I I is called conditionally negative definite if it is hermitian and
⟨ f , Ψ f ⟩ = ∑ i , j ∈ I ψ ( i , j ) f ( i ) ‾ f ( j ) ≤ 0 \langle f,\Psi f\rangle=\sum_{i,j\in I}\psi(i,j)\overline{f(i)}f(j)\leq0 ⟨ f , Ψ f ⟩ = i , j ∈ I ∑ ψ ( i , j ) f ( i ) f ( j ) ≤ 0
for any f ∈ C 0 ( I ; C ) f\in C_{0}(I;\mathbb{C}) f ∈ C 0 ( I ; C ) with ⟨ 1 , f ⟩ = 0 \langle\mathbf{1},f\rangle=0 ⟨ 1 , f ⟩ = 0 .
Lemma 5.1. Let ψ \psi ψ be a positive definite kernel on I I I . Then we have
∣ ∑ i ∈ I ψ ( o , i ) f ( i ) ∣ 2 ≤ ψ ( o , o ) ⟨ f , Ψ f ⟩ , o ∈ I , f ∈ C 0 ( I ; C ) . \left|\sum_{i\in I}\psi(o,i)f(i)\right|^{2}\leq\psi(o,o)\langle f,\Psi f\rangle,\qquad o\in I,\quad f\in C_{0}(I;\mathbb{C}). i ∈ I ∑ ψ ( o , i ) f ( i ) 2 ≤ ψ ( o , o ) ⟨ f , Ψ f ⟩ , o ∈ I , f ∈ C 0 ( I ; C ) .
Proof. We need only employ a standard argument using the Cauchy–Schwarz inequality, based on the fact that ⟨ f + λ δ o , Ψ ( f + λ δ o ) ⟩ ≥ 0 \langle f+\lambda\delta_o,\Psi(f+\lambda\delta_o)\rangle\geq0 ⟨ f + λ δ o , Ψ ( f + λ δ o )⟩ ≥ 0 for all λ ∈ C \lambda\in\mathbb{C} λ ∈ C , where δ o ∈ C 0 ( I ) \delta_o\in C_{0}(I) δ o ∈ C 0 ( I ) is defined by δ o ( o ) = 1 \delta_o(o)=1 δ o ( o ) = 1 and δ o ( i ) = 0 \delta_o(i)=0 δ o ( i ) = 0 for i ≠ o i\ne o i = o .
Lemma 5.2. For a kernel ψ \psi ψ on I I I the following two conditions are equivalent:
(i) ψ \psi ψ is conditionally negative definite;
(ii) the kernel defined by e − t ψ ( i , j ) = exp ( − t ψ ( i , j ) ) e^{-t\psi(i,j)}=\exp(-t\psi(i,j)) e − t ψ ( i , j ) = exp ( − t ψ ( i , j )) is positive definite for all t > 0 t>0 t > 0 .
The above result is well known in harmonic analysis and is often referred to as Schoenberg’s theorem [7 , 36 ] . The kernel e − t ψ e^{-t\psi} e − t ψ introduced in (ii) is also called the Hadamard exponential , which coincides with the entry-wise exponential in a matrix form.
Positive Definite Kernels on Block Graphs
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 . We will construct a positive definite kernel on V V V by concatenating ‘local kernels’ along a geodesic in G G G . This method was first introduced for constructing positive definite kernels on a tree [24 ] , for relevant results, see also [22 , 23 , 44 ] .
For a vertex v 0 ∈ V v_0\in V v 0 ∈ V let V ( v 0 ) \mathcal{V}(v_0) V ( v 0 ) denote the set of connected components of G ∖ { v 0 } G\setminus\{v_0\} G ∖ { v 0 } . Then we come to a partition of V V V defined by
V ′ ( v 0 ) = V ( v 0 ) ∪ { { v 0 } } , \mathcal{V}'(v_0)=\mathcal{V}(v_0)\cup\{\{v_0\}\}, V ′ ( v 0 ) = V ( v 0 ) ∪ {{ v 0 }} ,
and V V V is decomposed into a disjoint union of non-empty subsets:
V = ⋃ U ∈ V ′ ( v 0 ) U = { v 0 } ∪ ⋃ U ∈ V ( v 0 ) U . (28) V=\bigcup_{U\in\mathcal{V}'(v_0)}U=\{v_0\}\cup\bigcup_{U\in\mathcal{V}(v_0)}U. \tag*{(28)} V = U ∈ V ′ ( v 0 ) ⋃ U = { v 0 } ∪ U ∈ V ( v 0 ) ⋃ U . (28)
Note that the number of connected components in V ( v 0 ) \mathcal{V}(v_0) V ( v 0 ) coincides with cd ( v 0 ) \operatorname{cd}(v_0) cd ( v 0 ) .
Assume that each vertex v 0 ∈ V v_0\in V v 0 ∈ V is assigned a hermitian kernel on V ′ ( v 0 ) \mathcal{V}'(v_0) V ′ ( v 0 ) . We call the set { a v 0 ; v 0 ∈ V } \{a_{v_0};v_0\in V\} { a v 0 ; v 0 ∈ V } a system of local hermitian kernels . For a local hermitian kernel a v 0 a_{v_0} a v 0 we define a ( x , v 0 , y ) a(x,v_0,y) a ( x , v 0 , y ) for x , y ∈ V x,y\in V x , y ∈ V with d ( x , v 0 ) ≤ 1 d(x,v_0)\le1 d ( x , v 0 ) ≤ 1 and d ( y , v 0 ) ≤ 1 d(y,v_0)\le1 d ( y , v 0 ) ≤ 1 in such a way that
a ( x , v 0 , y ) = a v 0 ( U , W ) , U , W ∈ V ′ ( v 0 ) , x ∈ U , y ∈ W , (29) a(x,v_0,y)=a_{v_0}(U,W),\qquad U,W\in\mathcal{V}'(v_0),\quad x\in U,\quad y\in W, \tag*{(29)} a ( x , v 0 , y ) = a v 0 ( U , W ) , U , W ∈ V ′ ( v 0 ) , x ∈ U , y ∈ W , (29)
where U U U and W W W are uniquely determined by (28) . For (29) we also write
a ( x , v 0 , y ) = a ( U , v 0 , y ) = a ( x , v 0 , W ) = a ( U , v 0 , W ) (30) a(x,v_0,y)=a(U,v_0,y)=a(x,v_0,W)=a(U,v_0,W) \tag*{(30)} a ( x , v 0 , y ) = a ( U , v 0 , y ) = a ( x , v 0 , W ) = a ( U , v 0 , W ) (30)
for convenience.
Let { a v 0 ; v 0 ∈ V } \{a_{v_0};v_0\in V\} { a v 0 ; v 0 ∈ V } be a system of local hermitian kernels, and assume that a v 0 a_{v_0} a v 0 is positive definite for all v 0 ∈ V v_0\in V v 0 ∈ V and a v 0 ( U , U ) = 1 a_{v_0}(U,U)=1 a v 0 ( U , U ) = 1 for all U ∈ V ′ ( v 0 ) U\in\mathcal{V}'(v_0) U ∈ V ′ ( v 0 ) . Note the obvious relation:
a ( x , v 0 , y ) = 1 , x , y ∈ U , U ∈ V ′ ( v 0 ) . a(x,v_0,y)=1,\qquad x,y\in U,\quad U\in\mathcal{V}'(v_0). a ( x , v 0 , y ) = 1 , x , y ∈ U , U ∈ V ′ ( v 0 ) .
We now define a ‘global’ kernel on V V V by concatenating local kernels along a geodesic. Since G G G is geodetic by Proposition 3.12 , for any pair of vertices x , y ∈ V x,y\in V x , y ∈ V there exists a unique shortest path (the geodesic) connecting x x x and y y y , denoted by
x = x 0 ∼ x 1 ∼ x 2 ∼ ⋯ ∼ x n = y , n = d ( x , y ) . (31) x=x_0\sim x_1\sim x_2\sim\cdots\sim x_n=y,\qquad n=d(x,y). \tag*{(31)} x = x 0 ∼ x 1 ∼ x 2 ∼ ⋯ ∼ x n = y , n = d ( x , y ) . (31)
Along this geodesic we define a kernel on V V V by
ϕ ( x , y ) = ∏ k = 0 n a ( x k − 1 , x k , x k + 1 ) (32) \phi(x,y)=\prod_{k=0}^{n}a(x_{k-1},x_k,x_{k+1}) \tag*{(32)} ϕ ( x , y ) = k = 0 ∏ n a ( x k − 1 , x k , x k + 1 ) (32)
under the convention that x − 1 = x 0 = x x_{-1}=x_0=x x − 1 = x 0 = x and x n + 1 = x n = y x_{n+1}=x_n=y x n + 1 = x n = y . It is easy to see that ϕ \phi ϕ becomes a hermitian kernel on V V V satisfying ϕ ( x , x ) = 1 \phi(x,x)=1 ϕ ( x , x ) = 1 for all x ∈ V x\in V x ∈ V . We then define an auxiliary kernel by
β ( x , y ) = ∏ k = 0 n − 1 a ( x k − 1 , x k , x k + 1 ) , (33) \beta(x,y)=\prod_{k=0}^{n-1}a(x_{k-1},x_k,x_{k+1}), \tag*{(33)} β ( x , y ) = k = 0 ∏ n − 1 a ( x k − 1 , x k , x k + 1 ) , (33)
where (31) is taken into account with the convention that x − 1 = x 0 = x x_{-1}=x_0=x x − 1 = x 0 = x . By definition β ( x , x ) = 1 \beta(x,x)=1 β ( x , x ) = 1 for all x ∈ V x\in V x ∈ V . We see easily that
ϕ ( x , y ) = a ( x , x , y ) a ( x , y , y ) = β ( x , y ) β ( y , x ) ‾ , x , y ∈ V , x ∼ y . \phi(x,y)=a(x,x,y)a(x,y,y)=\beta(x,y)\overline{\beta(y,x)},\qquad x,y\in V,\quad x\sim y. ϕ ( x , y ) = a ( x , x , y ) a ( x , y , y ) = β ( x , y ) β ( y , x ) , x , y ∈ V , x ∼ y .
Moreover, for x , y ∈ V x,y\in V x , y ∈ V as in (31) we have
ϕ ( x , y ) = β ( x , x k ) a ( x k − 1 , x k , x k + 1 ) β ( y , x k ) ‾ , k = 0 , 1 , … , n . (34) \phi(x,y)=\beta(x,x_k)a(x_{k-1},x_k,x_{k+1})\overline{\beta(y,x_k)},\qquad k=0,1,\ldots,n. \tag*{(34)} ϕ ( x , y ) = β ( x , x k ) a ( x k − 1 , x k , x k + 1 ) β ( y , x k ) , k = 0 , 1 , … , n . (34)
We mention two more formulas for ϕ \phi ϕ in the following lemmas.
Lemma 5.3. Let v 0 ∈ V v_0\in V v 0 ∈ V and U , W ∈ V ( v 0 ) U,W\in\mathcal{V}(v_0) U , W ∈ V ( v 0 ) with U ≠ W U\ne W U = W . Then we have
ϕ ( x , y ) = β ( x , v 0 ) a v 0 ( U , W ) β ( y , v 0 ) ‾ , x ∈ U , y ∈ W . \phi(x,y)=\beta(x,v_0)a_{v_0}(U,W)\overline{\beta(y,v_0)},\qquad x\in U,\quad y\in W. ϕ ( x , y ) = β ( x , v 0 ) a v 0 ( U , W ) β ( y , v 0 ) , x ∈ U , y ∈ W . Proof. Noting that x ≠ v 0 x\ne v_0 x = v 0 and y ≠ v 0 y\ne v_0 y = v 0 , we take the geodesics
v 0 = x 0 ∼ x 1 ∼ ⋯ ∼ x s = x , v 0 = y 0 ∼ y 1 ∼ ⋯ ∼ y t = y . v_0=x_0\sim x_1\sim\cdots\sim x_s=x,\qquad v_0=y_0\sim y_1\sim\cdots\sim y_t=y. v 0 = x 0 ∼ x 1 ∼ ⋯ ∼ x s = x , v 0 = y 0 ∼ y 1 ∼ ⋯ ∼ y t = y . By assumption we have s , t ≥ 1 s,t\ge1 s , t ≥ 1 , x 1 ∈ U x_1\in U x 1 ∈ U , y 1 ∈ W y_1\in W y 1 ∈ W , and
x s ∼ x s − 1 ∼ ⋯ ∼ x 1 ∼ x 0 = v 0 = y 0 ∼ y 1 ∼ y 2 ∼ ⋯ ∼ y t x_s\sim x_{s-1}\sim\cdots\sim x_1\sim x_0=v_0=y_0\sim y_1\sim y_2\sim\cdots\sim y_t x s ∼ x s − 1 ∼ ⋯ ∼ x 1 ∼ x 0 = v 0 = y 0 ∼ y 1 ∼ y 2 ∼ ⋯ ∼ y t becomes the geodesic from x x x to y y y . Then the assertion follows by (34) . □ \square □
Lemma 5.4. Let v 0 ∈ V v_0\in V v 0 ∈ V and U ∈ V ( v 0 ) U\in\mathcal{V}(v_0) U ∈ V ( v 0 ) . For any x , y ∈ U x,y\in U x , y ∈ U satisfying d ( x , v 0 ) + d ( y , v 0 ) = d ( x , y ) + 1 d(x,v_0)+d(y,v_0)=d(x,y)+1 d ( x , v 0 ) + d ( y , v 0 ) = d ( x , y ) + 1 we have
ϕ ( x , y ) = β ( x , v 0 ) β ( y , v 0 ) ‾ . (35) \phi(x,y)=\beta(x,v_0)\overline{\beta(y,v_0)}. \tag*{(35)} ϕ ( x , y ) = β ( x , v 0 ) β ( y , v 0 ) . (35) Proof. Noting that x ≠ v 0 x\ne v_0 x = v 0 and y ≠ v 0 y\ne v_0 y = v 0 , we take the geodesics
v 0 = x 0 ∼ x 1 ∼ ⋯ ∼ x s = x , v 0 = y 0 ∼ y 1 ∼ ⋯ ∼ y t = y . v_0=x_0\sim x_1\sim\cdots\sim x_s=x,\qquad v_0=y_0\sim y_1\sim\cdots\sim y_t=y. v 0 = x 0 ∼ x 1 ∼ ⋯ ∼ x s = x , v 0 = y 0 ∼ y 1 ∼ ⋯ ∼ y t = y . By assumption we have s , t ≥ 1 s,t\ge1 s , t ≥ 1 , x 1 ≠ y 1 x_1\ne y_1 x 1 = y 1 , x 1 ∼ y 1 x_1\sim y_1 x 1 ∼ y 1 , and
x s ∼ x s − 1 ∼ ⋯ ∼ x 1 ∼ y 1 ∼ y 2 ∼ ⋯ ∼ y t x_s\sim x_{s-1}\sim\cdots\sim x_1\sim y_1\sim y_2\sim\cdots\sim y_t x s ∼ x s − 1 ∼ ⋯ ∼ x 1 ∼ y 1 ∼ y 2 ∼ ⋯ ∼ y t becomes the geodesic from x x x to y y y . Then (35) follows by (32) and (33) . □ \square □
We define a quadratic function by
Q ( f ) = ∑ x , y ∈ V ϕ ( x , y ) f ( x ) f ( y ) ‾ , f ∈ C 0 ( V ) . (36) Q(f)=\sum_{x,y\in V}\phi(x,y)f(x)\overline{f(y)},\qquad f\in C_0(V). \tag*{(36)} Q ( f ) = x , y ∈ V ∑ ϕ ( x , y ) f ( x ) f ( y ) , f ∈ C 0 ( V ) . (36)
Note that Q ( f ) = ⟨ f , Φ f ⟩ Q(f)=\langle f,\Phi f\rangle Q ( f ) = ⟨ f , Φ f ⟩ in terms of the standard inner product and the matrix notation Φ = [ ϕ ( x , y ) ] \Phi=[\phi(x,y)] Φ = [ ϕ ( x , y )] . We then see that the kernel ϕ ( x , y ) \phi(x,y) ϕ ( x , y ) is positive definite if Q ( f ) ≥ 0 Q(f)\ge0 Q ( f ) ≥ 0 for all f ∈ C 0 ( V ) f\in C_0(V) f ∈ C 0 ( V ) . The use of Q ( f ) Q(f) Q ( f ) is convenient for later argument.
To simplify the notation, we define a ‘localization’ of f ∈ C 0 ( V ) f\in C_0(V) f ∈ C 0 ( V ) by
B v 0 f ( U ) = ∑ x ∈ U β ( x , v 0 ) f ( x ) , U ∈ V ′ ( v 0 ) , f ∈ C 0 ( V ) . (37) B_{v_0}f(U)=\sum_{x\in U}\beta(x,v_0)f(x),\qquad U\in\mathcal{V}'(v_0),\quad f\in C_0(V). \tag*{(37)} B v 0 f ( U ) = x ∈ U ∑ β ( x , v 0 ) f ( x ) , U ∈ V ′ ( v 0 ) , f ∈ C 0 ( V ) . (37)
Obviously, B v 0 f ∈ C 0 ( V ′ ( v 0 ) ) B_{v_0}f\in C_0(\mathcal{V}'(v_0)) B v 0 f ∈ C 0 ( V ′ ( v 0 )) . We set
Q v 0 ( f ) = ∑ U , W ∈ V ′ ( v 0 ) a v 0 ( U , W ) B v 0 f ( U ) B v 0 f ( W ) ‾ , f ∈ C 0 ( V ) . (38) Q_{v_0}(f)=\sum_{U,W\in\mathcal{V}'(v_0)}a_{v_0}(U,W)B_{v_0}f(U)\overline{B_{v_0}f(W)},\qquad f\in C_0(V). \tag*{(38)} Q v 0 ( f ) = U , W ∈ V ′ ( v 0 ) ∑ a v 0 ( U , W ) B v 0 f ( U ) B v 0 f ( W ) , f ∈ C 0 ( V ) . (38)
Lemma 5.5. For any v 0 ∈ V v_0 \in V v 0 ∈ V and f ∈ C 0 ( V ) f \in C_0(V) f ∈ C 0 ( V ) we have
Q ( f ) − Q v 0 ( f ) = ∑ U ∈ V ( v 0 ) { Q ( f ∣ U ) − Q v 0 ( f ∣ U ) } . (39) Q(f)-Q_{v_0}(f)=\sum_{U\in\mathcal{V}(v_0)}\left\{Q(f|_U)-Q_{v_0}(f|_U)\right\}. \tag*{(39)} Q ( f ) − Q v 0 ( f ) = U ∈ V ( v 0 ) ∑ { Q ( f ∣ U ) − Q v 0 ( f ∣ U ) } . (39) where f ∣ U ∈ C 0 ( V ) f|_U \in C_0(V) f ∣ U ∈ C 0 ( V ) is defined by f ∣ U ( x ) = f ( x ) f|_U(x)=f(x) f ∣ U ( x ) = f ( x ) for x ∈ U x\in U x ∈ U and = 0 =0 = 0 otherwise.
Proof. According to the partition of V V V in (28) the quadratic function (36) becomes
Q ( f ) = ∣ f ( v 0 ) ∣ 2 + ∑ U ∈ V ( v 0 ) ∑ x , y ∈ U ϕ ( x , y ) f ( x ) f ( y ) ‾ + ∑ U , W ∈ V ′ ( v 0 ) U ≠ W ∑ x ∈ U y ∈ W ϕ ( x , y ) f ( x ) f ( y ) ‾ . (40) \begin{aligned}
Q(f)&=|f(v_0)|^2+\sum_{U\in\mathcal{V}(v_0)}\sum_{x,y\in U}\phi(x,y)f(x)\overline{f(y)}\\
&\quad+\sum_{\substack{U,W\in\mathcal{V}'(v_0)\\U\ne W}}\sum_{\substack{x\in U\\y\in W}}\phi(x,y)f(x)\overline{f(y)}. \tag*{(40)}
\end{aligned} Q ( f ) = ∣ f ( v 0 ) ∣ 2 + U ∈ V ( v 0 ) ∑ x , y ∈ U ∑ ϕ ( x , y ) f ( x ) f ( y ) + U , W ∈ V ′ ( v 0 ) U = W ∑ x ∈ U y ∈ W ∑ ϕ ( x , y ) f ( x ) f ( y ) . (40)
The second term becomes
∑ U ∈ V ( v 0 ) ∑ x , y ∈ U ϕ ( x , y ) f ( x ) f ( y ) ‾ = ∑ U ∈ V ( v 0 ) ∑ x , y ∈ V ϕ ( x , y ) f ∣ U ( x ) f ∣ U ( y ) ‾ = ∑ U ∈ V ( v 0 ) Q ( f ∣ U ) . (41) \begin{aligned}
\sum_{U\in\mathcal{V}(v_0)}\sum_{x,y\in U}\phi(x,y)f(x)\overline{f(y)}
&=\sum_{U\in\mathcal{V}(v_0)}\sum_{x,y\in V}\phi(x,y)f|_U(x)\overline{f|_U(y)}\\
&=\sum_{U\in\mathcal{V}(v_0)}Q(f|_U). \tag*{(41)}
\end{aligned} U ∈ V ( v 0 ) ∑ x , y ∈ U ∑ ϕ ( x , y ) f ( x ) f ( y ) = U ∈ V ( v 0 ) ∑ x , y ∈ V ∑ ϕ ( x , y ) f ∣ U ( x ) f ∣ U ( y ) = U ∈ V ( v 0 ) ∑ Q ( f ∣ U ) . (41)
For the third term, in view of Lemma 5.3 and (38) we come to
∑ U , W ∈ V ′ ( v 0 ) U ≠ W ∑ x ∈ U y ∈ W ϕ ( x , y ) f ( x ) f ( y ) ‾ = ∑ U , W ∈ V ′ ( v 0 ) U ≠ W a v 0 ( U , W ) B v 0 f ( U ) B v 0 f ( W ) ‾ = Q v 0 ( f ) − ∑ U ∈ V ′ ( v 0 ) a v 0 ( U , U ) ∣ B v 0 f ( U ) ∣ 2 . (42) \begin{aligned}
\sum_{\substack{U,W\in\mathcal{V}'(v_0)\\U\ne W}}\sum_{\substack{x\in U\\y\in W}}\phi(x,y)f(x)\overline{f(y)}
&=\sum_{\substack{U,W\in\mathcal{V}'(v_0)\\U\ne W}}a_{v_0}(U,W)B_{v_0}f(U)\overline{B_{v_0}f(W)}\\
&=Q_{v_0}(f)-\sum_{U\in\mathcal{V}'(v_0)}a_{v_0}(U,U)|B_{v_0}f(U)|^2. \tag*{(42)}
\end{aligned} U , W ∈ V ′ ( v 0 ) U = W ∑ x ∈ U y ∈ W ∑ ϕ ( x , y ) f ( x ) f ( y ) = U , W ∈ V ′ ( v 0 ) U = W ∑ a v 0 ( U , W ) B v 0 f ( U ) B v 0 f ( W ) = Q v 0 ( f ) − U ∈ V ′ ( v 0 ) ∑ a v 0 ( U , U ) ∣ B v 0 f ( U ) ∣ 2 . (42)
Since B v 0 f ∣ U ( W ) = B v 0 f ( U ) B_{v_0}f|_U(W)=B_{v_0}f(U) B v 0 f ∣ U ( W ) = B v 0 f ( U ) for W = U W=U W = U and = 0 =0 = 0 otherwise, we see that
∑ U ∈ V ′ ( v 0 ) a v 0 ( U , U ) ∣ B v 0 f ( U ) ∣ 2 = ∑ U ∈ V ′ ( v 0 ) ∑ U ′ , W ′ ∈ V ′ ( v 0 ) a v 0 ( U ′ , W ′ ) B v 0 f ∣ U ( U ′ ) B v 0 f ∣ U ( W ′ ) ‾ = ∣ f ( v 0 ) ∣ 2 + ∑ U ∈ V ( v 0 ) Q v 0 ( f ∣ U ) . (43) \begin{aligned}
\sum_{U\in\mathcal{V}'(v_0)}a_{v_0}(U,U)|B_{v_0}f(U)|^2
&=\sum_{U\in\mathcal{V}'(v_0)}\sum_{U',W'\in\mathcal{V}'(v_0)}a_{v_0}(U',W')B_{v_0}f|_U(U')\overline{B_{v_0}f|_U(W')}\\
&=|f(v_0)|^2+\sum_{U\in\mathcal{V}(v_0)}Q_{v_0}(f|_U). \tag*{(43)}
\end{aligned} U ∈ V ′ ( v 0 ) ∑ a v 0 ( U , U ) ∣ B v 0 f ( U ) ∣ 2 = U ∈ V ′ ( v 0 ) ∑ U ′ , W ′ ∈ V ′ ( v 0 ) ∑ a v 0 ( U ′ , W ′ ) B v 0 f ∣ U ( U ′ ) B v 0 f ∣ U ( W ′ ) = ∣ f ( v 0 ) ∣ 2 + U ∈ V ( v 0 ) ∑ Q v 0 ( f ∣ U ) . (43)
Then (39) follows by combining (40) –(43) . □
Now we are ready to prove the main result of this section.
Theorem 5.6. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph and { a v 0 ; v 0 ∈ V } \{a_{v_0};\,v_0\in V\} { a v 0 ; v 0 ∈ V } a system of local hermitian kernels satisfying a v 0 ( U , U ) = 1 a_{v_0}(U,U)=1 a v 0 ( U , U ) = 1 for any U ∈ V ′ ( v 0 ) U\in\mathcal{V}'(v_0) U ∈ V ′ ( v 0 ) . Define a hermitian kernel ϕ \phi ϕ on V V V as in (32) . If a v 0 a_{v_0} a v 0 is positive definite for all v 0 ∈ V v_0\in V v 0 ∈ V , so is ϕ \phi ϕ .
:::`
Proof. We need to show that Q ( f ) ≥ 0 Q(f) \ge0 Q ( f ) ≥ 0 for any f ∈ C 0 ( V ) f \in C_{0}(V) f ∈ C 0 ( V ) , where Q ( f ) Q(f) Q ( f ) is a quadratic function defined in (36) . Since a v 0 a_{v_{0}} a v 0 is positive definite by assumption, we see from (38) that Q v 0 ( f ) ≥ 0 Q_{v_{0}}(f) \ge0 Q v 0 ( f ) ≥ 0 for any v 0 ∈ V v_{0} \in V v 0 ∈ V and f ∈ C 0 ( V ) f \in C_{0}(V) f ∈ C 0 ( V ) . We set
Δ ( v 0 , f ) = Q ( f ) − Q v 0 ( f ) (44) \Delta(v_{0},f)=Q(f)-Q_{v_{0}}(f) \tag*{(44)} Δ ( v 0 , f ) = Q ( f ) − Q v 0 ( f ) (44)
Thus, for Q ( f ) ≥ 0 Q(f) \ge0 Q ( f ) ≥ 0 it is sufficient to show that Δ ( v 0 , f ) ≥ 0 \Delta(v_{0},f) \ge0 Δ ( v 0 , f ) ≥ 0 for any v 0 ∈ V v_{0} \in V v 0 ∈ V and f ∈ C 0 ( V ) f \in C_{0}(V) f ∈ C 0 ( V ) . In fact, by induction we prove the following statement: for each n ≥ 0 n \ge0 n ≥ 0 it holds that Δ ( v 0 , f ) ≥ 0 \Delta(v_{0},f) \ge0 Δ ( v 0 , f ) ≥ 0 for any v 0 ∈ V v_{0} \in V v 0 ∈ V and f ∈ C 0 ( V ) f \in C_{0}(V) f ∈ C 0 ( V ) satisfying supp ( f ) ⊂ { x ∈ V ; d ( v 0 , x ) ≤ n } \operatorname{supp}(f) \subset\{x \in V\,;\,d(v_{0},x) \le n\} supp ( f ) ⊂ { x ∈ V ; d ( v 0 , x ) ≤ n } .
For n = 0 n=0 n = 0 , the statement is obvious from
Δ ( v 0 , f ) = ϕ ( v 0 , v 0 ) f ( v 0 ) 2 − a v 0 ( { v 0 } , { v 0 } ) f ( v 0 ) 2 = 0. \Delta(v_{0},f)=\phi(v_{0},v_{0})f(v_{0})^{2}-a_{v_{0}}(\{v_{0}\},\{v_{0}\})f(v_{0})^{2}=0. Δ ( v 0 , f ) = ϕ ( v 0 , v 0 ) f ( v 0 ) 2 − a v 0 ({ v 0 } , { v 0 }) f ( v 0 ) 2 = 0.
Let n ≥ 1 n \ge1 n ≥ 1 and assume that the statement is true up to n − 1 n-1 n − 1 . Now let v 0 ∈ V v_{0} \in V v 0 ∈ V and f ∈ C 0 ( V ) f \in C_{0}(V) f ∈ C 0 ( V ) with supp ( f ) ⊂ { x ∈ V ; d ( v 0 , v ) ≤ n } \operatorname{supp}(f) \subset\{x \in V\,;\,d(v_{0},v) \le n\} supp ( f ) ⊂ { x ∈ V ; d ( v 0 , v ) ≤ n } . With the help of Lemma 5.5 we have
Δ ( v 0 , f ) = ∑ U ∈ V ( v 0 ) Δ ( v 0 , f ∣ U ) . (45) \Delta(v_{0},f)=\sum_{U\in\mathcal{V}(v_{0})}\Delta(v_{0},f|_{U}). \tag*{(45)} Δ ( v 0 , f ) = U ∈ V ( v 0 ) ∑ Δ ( v 0 , f ∣ U ) . (45)
We will show that Δ ( v 0 , f ∣ U 0 ) ≥ 0 \Delta(v_{0},f|_{U_{0}}) \ge0 Δ ( v 0 , f ∣ U 0 ) ≥ 0 for any U 0 ∈ V ( v 0 ) U_{0} \in\mathcal{V}(v_{0}) U 0 ∈ V ( v 0 ) by further decomposing it into a sum of similar quadratic terms. We set K 0 = { v ∈ U 0 : v 0 ∼ v } K_{0}=\{v\in U_{0}:v_{0}\sim v\} K 0 = { v ∈ U 0 : v 0 ∼ v } . Then K 0 ∪ { v 0 } K_{0}\cup\{v_{0}\} K 0 ∪ { v 0 } is a maximal clique of G G G , and any geodesic connecting x ∈ U 0 x\in U_{0} x ∈ U 0 and v 0 v_{0} v 0 passes through a unique vertex in K 0 K_{0} K 0 . We set
V v = { x ∈ U 0 : d ( x , v 0 ) = d ( x , v ) + 1 } , v ∈ K 0 . V_{v}=\{x\in U_{0}:d(x,v_{0})=d(x,v)+1\},\qquad v\in K_{0}. V v = { x ∈ U 0 : d ( x , v 0 ) = d ( x , v ) + 1 } , v ∈ K 0 .
In other words, V v V_{v} V v is the set of vertices x ∈ U 0 x\in U_{0} x ∈ U 0 such that the geodesic connecting x x x and v 0 v_{0} v 0 passes through v v v , and thus U 0 U_{0} U 0 is decomposed into a union of disjoint subsets:
U 0 = ⋃ v ∈ K 0 V v . U_{0}=\bigcup_{v\in K_{0}}V_{v}. U 0 = v ∈ K 0 ⋃ V v .
For v 1 , v 2 ∈ K 0 v_{1},v_{2}\in K_{0} v 1 , v 2 ∈ K 0 with v 1 ≠ v 2 v_{1}\ne v_{2} v 1 = v 2 we have
d ( x , v 0 ) + d ( y , v 0 ) = d ( x , y ) + 1 , x ∈ V v 1 , y ∈ V v 2 . d(x,v_{0})+d(y,v_{0})=d(x,y)+1,\qquad x\in V_{v_{1}},\quad y\in V_{v_{2}}. d ( x , v 0 ) + d ( y , v 0 ) = d ( x , y ) + 1 , x ∈ V v 1 , y ∈ V v 2 .
Then, by an argument similar to the proof of Lemma 5.5 with the help of Lemma 5.4 we obtain
Δ ( v 0 , f ∣ U 0 ) = ∑ v ∈ K 0 Δ ( v 0 , f ∣ V v ) , (46) \Delta(v_{0},f|_{U_{0}})=\sum_{v\in K_{0}}\Delta(v_{0},f|_{V_{v}}), \tag*{(46)} Δ ( v 0 , f ∣ U 0 ) = v ∈ K 0 ∑ Δ ( v 0 , f ∣ V v ) , (46)
where
Δ ( v 0 , f ∣ V v ) = ∑ x , y ∈ V v ϕ ( x , y ) f ( x ) f ( y ) ‾ − ∣ ∑ x ∈ V v β ( x , v 0 ) f ( x ) ∣ 2 . (47) \Delta(v_{0},f|_{V_{v}})=\sum_{x,y\in V_{v}}\phi(x,y)f(x)\overline{f(y)}-\left|\sum_{x\in V_{v}}\beta(x,v_{0})f(x)\right|^{2}. \tag*{(47)} Δ ( v 0 , f ∣ V v ) = x , y ∈ V v ∑ ϕ ( x , y ) f ( x ) f ( y ) − x ∈ V v ∑ β ( x , v 0 ) f ( x ) 2 . (47)
We next take v 1 ∈ K 0 v_{1}\in K_{0} v 1 ∈ K 0 and consider Δ ( v 0 , f ∣ V v 1 ) \Delta(v_{0},f|_{V_{v_{1}}}) Δ ( v 0 , f ∣ V v 1 ) . Set V 0 ( v 1 ) = { X ∈ V ( v 1 ) : v 0 ∉ X } \mathcal{V}_{0}(v_{1})=\{X\in\mathcal{V}(v_{1}):v_{0}\notin X\} V 0 ( v 1 ) = { X ∈ V ( v 1 ) : v 0 ∈ / X } . For X ∈ V 0 ( v 1 ) X\in\mathcal{V}_{0}(v_{1}) X ∈ V 0 ( v 1 ) we have
β ( x , v 0 ) = β ( x , v 1 ) a ( X , v 1 , v 0 ) , x ∈ X . \beta(x,v_{0})=\beta(x,v_{1})a(X,v_{1},v_{0}),\qquad x\in X. β ( x , v 0 ) = β ( x , v 1 ) a ( X , v 1 , v 0 ) , x ∈ X .
Then (5.20) with v v v being replaced by v 1 v_1 v 1 becomes
Δ ( v 0 , f ∣ V v 1 ) = ∑ x , y ∈ V v 1 ϕ ( x , y ) f ( x ) f ( y ) ‾ − ∣ ∑ x ∈ V v 1 β ( x , v 0 ) f ( x ) ∣ 2 = ∑ x , y ∈ V v 1 ϕ ( x , y ) f ( x ) f ( y ) ‾ − ∣ ∑ X ∈ V 0 ( v 1 ) a ( X , v 1 , v 0 ) ∑ x ∈ X β ( x , v 1 ) f ( x ) ∣ 2 = ∑ x , y ∈ V v 1 ϕ ( x , y ) f ( x ) f ( y ) ‾ − ∣ ∑ X ∈ V 0 ( v 1 ) a v 1 ( X , { v 0 } ) B v 1 f ( X ) ∣ 2 . (48) \begin{aligned}
\Delta(v_0,f|_{V_{v_1}})&=\sum_{x,y\in V_{v_1}}\phi(x,y)f(x)\overline{f(y)}-\left|\sum_{x\in V_{v_1}}\beta(x,v_0)f(x)\right|^2\\
&=\sum_{x,y\in V_{v_1}}\phi(x,y)f(x)\overline{f(y)}-\left|\sum_{X\in\mathcal{V}_0(v_1)}a(X,v_1,v_0)\sum_{x\in X}\beta(x,v_1)f(x)\right|^2\\
&=\sum_{x,y\in V_{v_1}}\phi(x,y)f(x)\overline{f(y)}-\left|\sum_{X\in\mathcal{V}_0(v_1)}a_{v_1}(X,\{v_0\})B_{v_1}f(X)\right|^2. \tag*{(48)}
\end{aligned} Δ ( v 0 , f ∣ V v 1 ) = x , y ∈ V v 1 ∑ ϕ ( x , y ) f ( x ) f ( y ) − x ∈ V v 1 ∑ β ( x , v 0 ) f ( x ) 2 = x , y ∈ V v 1 ∑ ϕ ( x , y ) f ( x ) f ( y ) − X ∈ V 0 ( v 1 ) ∑ a ( X , v 1 , v 0 ) x ∈ X ∑ β ( x , v 1 ) f ( x ) 2 = x , y ∈ V v 1 ∑ ϕ ( x , y ) f ( x ) f ( y ) − X ∈ V 0 ( v 1 ) ∑ a v 1 ( X , { v 0 }) B v 1 f ( X ) 2 . (48)
Here we note that
∣ ∑ X ∈ V 0 ( v 1 ) a v 1 ( X , { v 0 } ) B v 1 f ( X ) ∣ 2 ≤ ∑ X , Y ∈ V 0 ( v 1 ) a v 1 ( X , Y ) B v 1 f ( X ) B v 1 f ( Y ) ‾ , (49) \left|\sum_{X\in\mathcal{V}_0(v_1)}a_{v_1}(X,\{v_0\})B_{v_1}f(X)\right|^2\leq\sum_{X,Y\in\mathcal{V}_0(v_1)}a_{v_1}(X,Y)B_{v_1}f(X)\overline{B_{v_1}f(Y)}, \tag*{(49)} X ∈ V 0 ( v 1 ) ∑ a v 1 ( X , { v 0 }) B v 1 f ( X ) 2 ≤ X , Y ∈ V 0 ( v 1 ) ∑ a v 1 ( X , Y ) B v 1 f ( X ) B v 1 f ( Y ) , (49)
which follows from the Schwarz inequality (Lemma 5.1) and a v 1 ( { v 0 } , { v 0 } ) = 1 a_{v_1}(\{v_0\},\{v_0\})=1 a v 1 ({ v 0 } , { v 0 }) = 1 . Applying (5.22) to (5.21), we obtain
Δ ( v 0 , f ∣ V v 1 ) ≥ ∑ x , y ∈ V v 1 ϕ ( x , y ) f ( x ) f ( y ) ‾ − ∑ X , Y ∈ V 0 ( v 1 ) a v 1 ( X , Y ) B v 1 f ( X ) B v 1 f ( Y ) ‾ = Δ ( v 1 , f ∣ V v 1 ) (50) \begin{aligned}
\Delta(v_0,f|_{V_{v_1}})&\geq\sum_{x,y\in V_{v_1}}\phi(x,y)f(x)\overline{f(y)}-\sum_{X,Y\in\mathcal{V}_0(v_1)}a_{v_1}(X,Y)B_{v_1}f(X)\overline{B_{v_1}f(Y)}\\
&=\Delta(v_1,f|_{V_{v_1}}) \tag*{(50)}
\end{aligned} Δ ( v 0 , f ∣ V v 1 ) ≥ x , y ∈ V v 1 ∑ ϕ ( x , y ) f ( x ) f ( y ) − X , Y ∈ V 0 ( v 1 ) ∑ a v 1 ( X , Y ) B v 1 f ( X ) B v 1 f ( Y ) = Δ ( v 1 , f ∣ V v 1 ) (50)
Since Δ ( v 1 , f ∣ V v 1 ) ≥ 0 \Delta(v_1,f|_{V_{v_1}})\geq0 Δ ( v 1 , f ∣ V v 1 ) ≥ 0 by the induction hypothesis, we have Δ ( v 0 , f ∣ V v 1 ) ≥ 0 \Delta(v_0,f|_{V_{v_1}})\geq0 Δ ( v 0 , f ∣ V v 1 ) ≥ 0 , that is, Δ ( v 0 , f ∣ V v ) ≥ 0 \Delta(v_0,f|_{V_v})\geq0 Δ ( v 0 , f ∣ V v ) ≥ 0 holds for any v ∈ K 0 v\in K_0 v ∈ K 0 . Then in view of (5.20) and (5.19) we have Δ ( v 0 , f ∣ U 0 ) ≥ 0 \Delta(v_0,f|_{U_0})\geq0 Δ ( v 0 , f ∣ U 0 ) ≥ 0 as desired. □
Conditionally Negative Definite Kernels on Block Graphs
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph and { c v 0 ; v 0 ∈ V } \{c_{v_0};v_0\in V\} { c v 0 ; v 0 ∈ V } a system of local hermitian kernels satisfying c v 0 ( U , U ) = 0 c_{v_0}(U,U)=0 c v 0 ( U , U ) = 0 for any U ∈ V ′ ( v 0 ) U\in\mathcal{V}'(v_0) U ∈ V ′ ( v 0 ) . In a similar manner as in Section 5.2, we define c ( x , v 0 , y ) c(x,v_0,y) c ( x , v 0 , y ) for x , y ∈ V x,y\in V x , y ∈ V with d ( x , v 0 ) ≤ 1 d(x,v_0)\leq1 d ( x , v 0 ) ≤ 1 and d ( y , v 0 ) ≤ 1 d(y,v_0)\leq1 d ( y , v 0 ) ≤ 1 , see (5.2). For any pair of vertices x , y ∈ V x,y\in V x , y ∈ V , taking the geodesic as in (5.4) we set
ψ ( x , y ) = ∑ i = 0 n c ( x i − 1 , x i , x i + 1 ) . (51) \psi(x,y)=\sum_{i=0}^{n}c(x_{i-1},x_i,x_{i+1}). \tag*{(51)} ψ ( x , y ) = i = 0 ∑ n c ( x i − 1 , x i , x i + 1 ) . (51)
We see easily that ψ \psi ψ becomes a hermitian kernel on V V V .
Theorem 5.7. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a block graph and { c v 0 ; v 0 ∈ V } \{c_{v_0};v_0\in V\} { c v 0 ; v 0 ∈ V } a system of local hermitian kernels satisfying c v 0 ( U , U ) = 0 c_{v_0}(U,U)=0 c v 0 ( U , U ) = 0 for any U ∈ V ′ ( v 0 ) U\in\mathcal{V}'(v_0) U ∈ V ′ ( v 0 ) . If c v 0 c_{v_0} c v 0 is conditionally negative definite for all v 0 ∈ V v_0\in V v 0 ∈ V , so is the hermitian kernel ψ \psi ψ defined in (5.24).
Proof. For v 0 ∈ V v_0\in V v 0 ∈ V and t > 0 t>0 t > 0 we define a kernel a v 0 , t a_{v_0,t} a v 0 , t on V ′ ( v 0 ) \mathcal{V}'(v_0) V ′ ( v 0 ) by
a v 0 , t ( U , W ) = exp ( − t c v 0 ( U , W ) ) , U , W ∈ V ′ ( v 0 ) . a_{v_0,t}(U,W)=\exp(-tc_{v_0}(U,W)),\qquad U,W\in\mathcal{V}'(v_0). a v 0 , t ( U , W ) = exp ( − t c v 0 ( U , W )) , U , W ∈ V ′ ( v 0 ) .
Since c v 0 c_{v_0} c v 0 is conditionally negative definite, the kernel a v 0 , t a_{v_0,t} a v 0 , t is positive definite for all t > 0 t > 0 t > 0 by Lemma 5.2 . It then follows from Theorem 5.6 that the hermitian kernel ϕ t \phi_t ϕ t on V V V defined by
ϕ t ( x , y ) = ∏ i = 0 n a t ( x i − 1 , x i , x i + 1 ) = ∏ i = 0 n exp ( − t c ( x i − 1 , x i , x i + 1 ) ) = exp ( − t ψ ( x , y ) ) \phi_t(x,y)=\prod_{i=0}^{n}a_t(x_{i-1},x_i,x_{i+1})=\prod_{i=0}^{n}\exp(-tc(x_{i-1},x_i,x_{i+1}))=\exp(-t\psi(x,y)) ϕ t ( x , y ) = i = 0 ∏ n a t ( x i − 1 , x i , x i + 1 ) = i = 0 ∏ n exp ( − t c ( x i − 1 , x i , x i + 1 )) = exp ( − t ψ ( x , y ))
is positive definite. Again by Lemma 5.2 we see that ψ \psi ψ is conditionally negative definite.
Proof of Theorem 4.1
We rely on the following elementary linear algebraic result.
Lemma 5.8. Let m ≥ 1 m \ge1 m ≥ 1 . For u ∈ R u \in\mathbb{R} u ∈ R let C u C_u C u be an ( m + 1 ) × ( m + 1 ) (m+1) \times(m+1) ( m + 1 ) × ( m + 1 ) matrix given in a block matrix form as
C u = [ 0 u 1 T u 1 J − I ] C_u=\begin{bmatrix}0 & u\mathbf{1}^{T}\\u\mathbf{1} & J-I\end{bmatrix} C u = [ 0 u 1 u 1 T J − I ] where 1 ∈ R m \mathbf{1} \in\mathbb{R}^{m} 1 ∈ R m is the column vector whose entries are all one, J J J the m × m m \times m m × m all-one matrix, and I I I the m × m m \times m m × m identity matrix. Then C u C_u C u is conditionally negative definite if and only if u ≥ ( m − 1 ) / ( 2 m ) u \ge(m-1)/(2m) u ≥ ( m − 1 ) / ( 2 m ) .
Proof of Theorem 4.1. We define a system of local hermitian kernels { c v 0 ; v 0 ∈ V } \{c_{v_0}; v_0 \in V\} { c v 0 ; v 0 ∈ V } by
c v 0 ( U , W ) = c v 0 ( W , U ) = { 0 , if U = W ∈ V ′ ( v 0 ) , p − 1 2 p , if U = { v 0 } , W ∈ V ( v 0 ) , 1 , if U , W ∈ V ( v 0 ) , U ≠ W . (52) c_{v_0}(U,W)=c_{v_0}(W,U)=
\begin{cases}
0, & \text{if } U=W\in\mathcal{V}'(v_0),\\
\frac{p-1}{2p}, & \text{if } U=\{v_0\}, W\in\mathcal{V}(v_0),\\
1, & \text{if } U,W\in\mathcal{V}(v_0), U\ne W.
\end{cases} \tag*{(52)} c v 0 ( U , W ) = c v 0 ( W , U ) = ⎩ ⎨ ⎧ 0 , 2 p p − 1 , 1 , if U = W ∈ V ′ ( v 0 ) , if U = { v 0 } , W ∈ V ( v 0 ) , if U , W ∈ V ( v 0 ) , U = W . (52)
In fact, c v 0 c_{v_0} c v 0 is a real symmetric kernel, and [ c v 0 ( U , W ) ] [c_{v_0}(U,W)] [ c v 0 ( U , W )] becomes an ( m + 1 ) × ( m + 1 ) (m+1)\times(m+1) ( m + 1 ) × ( m + 1 ) matrix with m = cd ( v 0 ) m=\operatorname{cd}(v_0) m = cd ( v 0 ) . Since m ≤ p m\le p m ≤ p , we see from Lemma 5.8 that the matrix [ c v 0 ( U , W ) ] [c_{v_0}(U,W)] [ c v 0 ( U , W )] is conditionally negative definite. Thus, { c v 0 ; v 0 ∈ V } \{c_{v_0}; v_0\in V\} { c v 0 ; v 0 ∈ V } is a system of local hermitian kernels such that c v 0 ( U , U ) = 0 c_{v_0}(U,U)=0 c v 0 ( U , U ) = 0 for all U ∈ V ′ ( v 0 ) U\in\mathcal{V}'(v_0) U ∈ V ′ ( v 0 ) and c v 0 c_{v_0} c v 0 is conditionally negative definite for all v 0 ∈ V v_0\in V v 0 ∈ V .
For x , y ∈ V x,y\in V x , y ∈ V taking the geodesic
x = x 0 ∼ x 1 ∼ ⋯ ∼ x n = y , d ( x , y ) = n , x=x_0\sim x_1\sim\cdots\sim x_n=y,\qquad d(x,y)=n, x = x 0 ∼ x 1 ∼ ⋯ ∼ x n = y , d ( x , y ) = n ,
we define
ψ ~ ( x , y ) = ∑ i = 0 n c ( x i − 1 , x i , x i + 1 ) . \widetilde{\psi}(x,y)=\sum_{i=0}^{n}c(x_{i-1},x_i,x_{i+1}). ψ ( x , y ) = i = 0 ∑ n c ( x i − 1 , x i , x i + 1 ) .
It then follows from Theorem 5.7 that ψ ~ \widetilde{\psi} ψ is a conditionally negative definite kernel on V V V . On the other hand, we see from (5.25) that
ψ ~ ( x , x ) = 0 , x ∈ V , \widetilde{\psi}(x,x)=0,\qquad x\in V, ψ ( x , x ) = 0 , x ∈ V ,
and if d ( x , y ) = n ≥ 1 d(x,y)=n\ge1 d ( x , y ) = n ≥ 1 we have
ψ ~ ( x , y ) = c ( x 0 , x 0 , x 1 ) + c ( x 0 , x 1 , x 2 ) + ⋯ + c ( x n − 2 , x n − 1 , x n ) + c ( x n − 1 , x n , x n ) = p − 1 2 p + ( n − 1 ) + p − 1 2 p = n − 1 p = d ( x , y ) − 1 p . \begin{aligned}
\widetilde{\psi}(x,y)=c(x_0,x_0,x_1)+c(x_0,x_1,x_2)+\cdots+c(x_{n-2},x_{n-1},x_n)+c(x_{n-1},x_n,x_n) \\
&=\frac{p-1}{2p}+(n-1)+\frac{p-1}{2p}=n-\frac{1}{p}=d(x,y)-\frac{1}{p}.
\end{aligned} ψ ( x , y ) = c ( x 0 , x 0 , x 1 ) + c ( x 0 , x 1 , x 2 ) + ⋯ + c ( x n − 2 , x n − 1 , x n ) + c ( x n − 1 , x n , x n ) = 2 p p − 1 + ( n − 1 ) + 2 p p − 1 = n − p 1 = d ( x , y ) − p 1 .
Therefore, ψ ~ \widetilde{\psi} ψ coincides with ψ \psi ψ given in the statement. Consequently, ψ \psi ψ is a conditionally negative definite kernel on V V V .
Some Remarks
Free Product of Complete Graphs
Let p ≥ 2 p\ge2 p ≥ 2 . For each i = 1 , 2 , … , p i=1,2,\ldots,p i = 1 , 2 , … , p let G i G_i G i be a finite or infinite complete garph and consider their free product:
G = G 1 ∗ G 2 ∗ ⋯ ∗ G p . (53) G=G_1\ast G_2\ast\cdots\ast G_p. \tag*{(53)} G = G 1 ∗ G 2 ∗ ⋯ ∗ G p . (53)
Let n i n_i n i be the number of vertices of G i G_i G i if it is finite, otherwise we set n i = ∞ n_i=\infty n i = ∞ . From now on, the free product (53) is simply denoted by
G = K n 1 ∗ K n 2 ∗ ⋯ ∗ K n p . (54) G=K_{n_1}\ast K_{n_2}\ast\cdots\ast K_{n_p}. \tag*{(54)} G = K n 1 ∗ K n 2 ∗ ⋯ ∗ K n p . (54)
An example is shown in Figure 2 . The free product G G G becomes an infinite block graph which is homogeneous in the sense that the subgraph induced by any vertex x x x of G G G and its adjacent ones is isomorphic to the star product K n 1 ⋆ K n 2 ⋆ ⋯ ⋆ K n p K_{n_1}\star K_{n_2}\star\cdots\star K_{n_p} K n 1 ⋆ K n 2 ⋆ ⋯ ⋆ K n p . We note that the degree and the clique degree are constant:
Figure 2. Star product K 2 ⋆ K 3 ⋆ K 4 K_2 \star K_3 \star K_4 K 2 ⋆ K 3 ⋆ K 4 and free product K 2 ⊛ K 3 ⊛ K 4 K_2 \circledast K_3 \circledast K_4 K 2 ⊛ K 3 ⊛ K 4
deg x = ∑ i = 1 p ( n i − 1 ) , cd ( x ) = p , x ∈ V . \deg x=\sum_{i=1}^{p}(n_i-1),\qquad\operatorname{cd}(x)=p,\qquad x\in V. deg x = i = 1 ∑ p ( n i − 1 ) , cd ( x ) = p , x ∈ V .
In general, the free product is defined for rooted graphs ( G i , o i ) (G_i,o_i) ( G i , o i ) but for complete graphs G i G_i G i we do not need to specify roots because of symmetry. For a general definition and further properties of free product graphs, see [9 , 38 , 45 ] .
Theorem 6.1. Let p ≥ 1 p\ge1 p ≥ 1 and n i ≥ 2 n_i\ge2 n i ≥ 2 or n i = ∞ n_i=\infty n i = ∞ for i = 1 , 2 , … , p i=1,2,\ldots,p i = 1 , 2 , … , p . If n i < ∞ n_i<\infty n i < ∞ for some i i i , setting n ∗ = min { n 1 , … , n p } < ∞ n_*=\min\{n_1,\ldots,n_p\}<\infty n ∗ = min { n 1 , … , n p } < ∞ , we have
− n ∗ p ( n ∗ − 1 ) + 1 ≤ QEC ( K n 1 ∗ K n 2 ∗ ⋯ ∗ K n p ) ≤ − 1 p . (55) -\frac{n_*}{p(n_*-1)+1}\le\operatorname{QEC}(K_{n_1}\ast K_{n_2}\ast\cdots\ast K_{n_p})\le-\frac{1}{p}. \tag*{(55)} − p ( n ∗ − 1 ) + 1 n ∗ ≤ QEC ( K n 1 ∗ K n 2 ∗ ⋯ ∗ K n p ) ≤ − p 1 . (55) Moreover, if n i = ∞ n_i=\infty n i = ∞ for all i = 1 , 2 , … , p i=1,2,\ldots,p i = 1 , 2 , … , p , we have
QEC ( K ∞ ∗ K ∞ ∗ ⋯ ∗ K ∞ ⏟ p t i m e s ) = QEC ( K ∞ ∗ p ) = − 1 p . (56) \operatorname{QEC}\left(\underbrace{K_\infty\ast K_\infty\ast\cdots\ast K_\infty}_{p\ \mathrm{times}}\right)=\operatorname{QEC}(K_\infty^{\ast p})=-\frac{1}{p}. \tag*{(56)} QEC p times K ∞ ∗ K ∞ ∗ ⋯ ∗ K ∞ = QEC ( K ∞ ∗ p ) = − p 1 . (56)
Proof. The right half of (55) follows directly from Theorem 4.2 , and the left half from Proposition 4.8. For (56) it is sufficient to let n ∗ → ∞ n_* \to\infty n ∗ → ∞ in (55) , see also Proposition 4.9.
Theorem 6.2. Let n i ≥ 2 n_i \ge2 n i ≥ 2 or n i = ∞ n_i = \infty n i = ∞ for i = 1 , 2 i = 1,2 i = 1 , 2 . Then the free product K n 1 ⊛ K n 2 K_{n_1} \circledast K_{n_2} K n 1 ⊛ K n 2 is an infinite cactus-like graph and we have
QEC ( K n 1 ⊛ K n 2 ) = − 1 2 . (57) \operatorname{QEC}(K_{n_1} \circledast K_{n_2}) = -\frac{1}{2}. \tag*{(57)} QEC ( K n 1 ⊛ K n 2 ) = − 2 1 . (57)
Proof. Setting p = 2 p=2 p = 2 in Theorem 6.1 we obtain
QEC ( G ) ≤ − 1 2 . (58) \operatorname{QEC}(G) \le-\frac{1}{2}. \tag*{(58)} QEC ( G ) ≤ − 2 1 . (58)
On the other hand, by construction G = K n 1 ⊛ K n 2 G = K_{n_1} \circledast K_{n_2} G = K n 1 ⊛ K n 2 contains K 2 ⊛ K 2 ≅ Z K_2 \circledast K_2 \cong\mathbb{Z} K 2 ⊛ K 2 ≅ Z (two-sided infinite path) as an isometric subgraph. Then, with the help of Propositions 2.1 and 2.2 we see that
− 1 2 = QEC ( Z ) ≤ QEC ( G ) . (59) -\frac{1}{2} = \operatorname{QEC}(\mathbb{Z}) \le\operatorname{QEC}(G). \tag*{(59)} − 2 1 = QEC ( Z ) ≤ QEC ( G ) . (59)
Then the assertion follows from (58) and (59) . An example of K n 1 ⊛ K n 2 K_{n_1} \circledast K_{n_2} K n 1 ⊛ K n 2 is shown in Figure 3 .
Figure 3. Free product graph K 3 ⊛ K 4 K_3 \circledast K_4 K 3 ⊛ K 4
Remark 6.3. The free product graph G = K n 1 ⊛ K n 2 ⊛ ⋯ ⊛ K n p G = K_{n_1} \circledast K_{n_2} \circledast\cdots\circledast K_{n_p} G = K n 1 ⊛ K n 2 ⊛ ⋯ ⊛ K n p is well understood as the Cayley graph of the free product group Γ = Γ 1 ⊛ Γ 2 ⊛ ⋯ ⊛ Γ p \Gamma= \Gamma_1 \circledast\Gamma_2 \circledast\cdots\circledast\Gamma_p Γ = Γ 1 ⊛ Γ 2 ⊛ ⋯ ⊛ Γ p , where Γ i \Gamma_i Γ i is a finite or infinite group consisting of n i n_i n i elements, with ⋃ i = 1 p Γ i ∖ { e } \bigcup_{i=1}^{p} \Gamma_i \setminus\{e\} ⋃ i = 1 p Γ i ∖ { e } as the set of generators. The length function on a free product group is important in harmonic analysis and has been studied considerably. Our argument for block graphs in § 5 is an extension of the result on Cayley graphs of free product groups developed in [22 , 23 , 24 , 44 ] .
Trees
A graph is called a homogeneous tree of degree p ≥ 2 p \ge2 p ≥ 2 , denoted by T p T_p T p , if it is a tree and the degree of every vertex coincides with p p p . For p = 1 p=1 p = 1 we may understand that T 1 = K 2 T_1=K_2 T 1 = K 2 though trivial. Obviously, we have
T p ≅ K 2 ⊛ p = K 2 ⊛ K 2 ⊛ ⋯ ⊛ K 2 ( p times ) . (60) T_p \cong K_2^{\circledast p}=K_2 \circledast K_2 \circledast\cdots\circledast K_2 \quad(p\text{ times}). \tag*{(60)} T p ≅ K 2 ⊛ p = K 2 ⊛ K 2 ⊛ ⋯ ⊛ K 2 ( p times ) . (60)
In particular, T 2 = K 2 ⊛ K 2 ≅ Z T_2=K_2 \circledast K_2 \cong\mathbb{Z} T 2 = K 2 ⊛ K 2 ≅ Z becomes a two-sided infinite path.
Proposition 6.4. Let T = ( V , E ) T=(V,E) T = ( V , E ) be a (finite or infinite) tree with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 and set p = sup { deg x ; x ∈ V } p=\sup\{\deg x; x\in V\} p = sup { deg x ; x ∈ V } . If 1 ≤ p < ∞ 1\le p<\infty 1 ≤ p < ∞ , we have
− 2 p + 1 ≤ QEC ( T ) ≤ − 1 p . (61) -\frac{2}{p+1}\le\operatorname{QEC}(T)\le-\frac{1}{p}. \tag*{(61)} − p + 1 2 ≤ QEC ( T ) ≤ − p 1 . (61) If p = ∞ p=\infty p = ∞ , we have QEC ( T ) = 0 \operatorname{QEC}(T)=0 QEC ( T ) = 0 .
Proof. Let T = ( V , E ) T=(V,E) T = ( V , E ) be a tree with ∣ V ∣ ≥ 2 |V|\ge2 ∣ V ∣ ≥ 2 and assume that 1 ≤ p < ∞ 1\le p<\infty 1 ≤ p < ∞ . Since T T T is isometrically embedded in the homogeneous tree T p T_p T p , we see that QEC ( T ) ≤ QEC ( T p ) \operatorname{QEC}(T)\le\operatorname{QEC}(T_p) QEC ( T ) ≤ QEC ( T p ) . Then the right half of (61) follows from Theorem 6.1. For the left half of (61) we take x ∈ V x\in V x ∈ V with deg x = p \deg x=p deg x = p . Let y 1 , … , y p ∈ V y_1,\ldots,y_p\in V y 1 , … , y p ∈ V be distinct vertices adjacent to x x x . Since T T T has no cycles, any pair of distinct y i y_i y i and y j y_j y j is not adjacent. Then the induced subgraph H = ⟨ x , y 1 , … , y p ⟩ H=\langle x,y_1,\ldots,y_p\rangle H = ⟨ x , y 1 , … , y p ⟩ is isomorphic to the complete bipartite graph K 1 , p K_{1,p} K 1 , p . Moreover, it is easy to see that H H H is an isometric subgraph of T T T . Thus, we obtain
QEC ( T ) ≥ QEC ( H ) = QEC ( K 1 , p ) = − 2 p + 1 , \operatorname{QEC}(T)\ge\operatorname{QEC}(H)=\operatorname{QEC}(K_{1,p})=-\frac{2}{p+1}, QEC ( T ) ≥ QEC ( H ) = QEC ( K 1 , p ) = − p + 1 2 , where the explicit value of QEC ( K 1 , p ) \operatorname{QEC}(K_{1,p}) QEC ( K 1 , p ) is known [35 ] . This proves the left half of (61) . The rest of the assertion is obtained by letting p → ∞ p\to\infty p → ∞ in (61) .
Remark 6.5. Let T T T be a tree on n ≥ 4 n\ge4 n ≥ 4 vertices. It is known [10 ] that
QEC ( P n ) ≤ QEC ( T ) ≤ QEC ( K 1 , n − 1 ) = − 2 n . \operatorname{QEC}(P_n)\le\operatorname{QEC}(T)\le\operatorname{QEC}(K_{1,n-1})=-\frac{2}{n}. QEC ( P n ) ≤ QEC ( T ) ≤ QEC ( K 1 , n − 1 ) = − n 2 .
This is the best possible estimate in terms of the number of vertices in the sense that both equalities are attained. Our result in Proposition 6.4 is an estimate of different type in terms of the maximal degree. It is desirable to obtain a sharp estimate of QEC ( T ) \operatorname{QEC}(T) QEC ( T ) for a tree T T T using other characteristics.
Further Remarks
Remark 6.6. Howorka [16 ] called a graph simple if every pair of distinct maximal cliques has at most one vertex in common. As this terminology is apparently confusing today, for the moment such a graph is called a H H H -graph. H H H -graphs are interesting from the point of view of metric properties. In this paper, we have established the following inclusion for connected graphs:
{ cactus-like graphs } ⊂ { block graphs } ⊂ { geodetic graphs } ⊂ { H -graphs } . \{\text{cactus-like graphs}\} \subset\{\text{block graphs}\} \subset\{\text{geodetic graphs}\} \subset\{\text{$H$-graphs}\}. { cactus-like graphs } ⊂ { block graphs } ⊂ { geodetic graphs } ⊂ { H -graphs } .
The study of QEC \operatorname{QEC} QEC along with metric properties would be an interesting future work.
Remark 6.7. The new term ‘cactus-like graph’ is motivated by ‘cactus graph,’ though the latter has been used with varying meanings in the literature. According to the fairly standard definition, a connected graph G = ( V , E ) G=(V,E) G = ( V , E ) is called a cactus if every 2-connected component is an edge or a cycle. In other words, a cactus is a connected graph in which any two distinct cycles have at most one vertex in common, or equivalently in which no edge lies on more than one cycle. By definition the singleton graph K 1 K_1 K 1 is a cactus. It is noted that cactus graphs and cactus-like graphs are distinct though the two classes overlap. When a cactus graph contains an even cycle, it is clear that QEC ( G ) = 0 \operatorname{QEC}(G)=0 QEC ( G ) = 0 . When a cactus graph contains no even cycle, further investigation is required.
Star Products of Complete Graphs
Let p ≥ 1 p\ge1 p ≥ 1 , n 1 ≥ 1 , … , n p ≥ 1 n_1\ge1,\ldots,n_p\ge1 n 1 ≥ 1 , … , n p ≥ 1 and consider the star product:
G = K n 1 + 1 ⋆ K n 2 + 1 ⋆ ⋯ ⋆ K n p + 1 . G=K_{n_1+1}\star K_{n_2+1}\star\cdots\star K_{n_p+1}. G = K n 1 + 1 ⋆ K n 2 + 1 ⋆ ⋯ ⋆ K n p + 1 .
The set of vertices of G G G is given as the disjoint union:
V = { o } ∪ V 1 ∪ V 2 ∪ ⋯ ∪ V p , (62) V=\{o\}\cup V_1\cup V_2\cup\cdots\cup V_p, \tag*{(62)} V = { o } ∪ V 1 ∪ V 2 ∪ ⋯ ∪ V p , (62)
where o o o is the root of G G G and { o } ∪ V i \{o\}\cup V_i { o } ∪ V i is the vertex set of K n i + 1 K_{n_i+1} K n i + 1 . Then, according to the direct sum decomposition:
C ( V ) = R ⊕ C ( V 1 ) ⊕ C ( V 2 ) ⊕ ⋯ ⊕ C ( V p ) , (63) \mathcal{C}(V)=\mathbb{R}\oplus\mathcal{C}(V_1)\oplus\mathcal{C}(V_2)\oplus\cdots\oplus\mathcal{C}(V_p), \tag*{(63)} C ( V ) = R ⊕ C ( V 1 ) ⊕ C ( V 2 ) ⊕ ⋯ ⊕ C ( V p ) , (63)
any column vector f ∈ C ( V ) f\in\mathcal{C}(V) f ∈ C ( V ) is expressed as
f = [ f 0 f 1 ⋮ f p ] , f 0 ∈ R , f i ∈ C ( V i ) ≅ R n i , i = 1 , 2 , … , p . f=
\begin{bmatrix}
f_0\\
f_1\\
\vdots\\
f_p
\end{bmatrix},
\qquad
f_0\in\mathbb{R},
\qquad
f_i\in\mathcal{C}(V_i)\cong\mathbb{R}^{n_i},
\quad i=1,2,\ldots,p. f = f 0 f 1 ⋮ f p , f 0 ∈ R , f i ∈ C ( V i ) ≅ R n i , i = 1 , 2 , … , p .
Moreover, based on (A.1) the distance matrix D D D of G G G is given as the block matrix of the form:
D = [ 0 J J ⋯ J J J − I 2 J ⋯ 2 J J 2 J J − I ⋯ 2 J ⋮ ⋮ ⋮ ⋱ ⋮ J 2 J 2 J ⋯ J − I ] , D=\begin{bmatrix}
0 & J & J & \cdots& J\\
J & J-I & 2J & \cdots& 2J\\
J & 2J & J-I & \cdots& 2J\\
\vdots& \vdots& \vdots& \ddots& \vdots\\
J & 2J & 2J & \cdots& J-I
\end{bmatrix}, D = 0 J J ⋮ J J J − I 2 J ⋮ 2 J J 2 J J − I ⋮ 2 J ⋯ ⋯ ⋯ ⋱ ⋯ J 2 J 2 J ⋮ J − I ,
where J J J is the all-one matrix and I I I the identity matrix of which the sizes are understood in the context. By definition QEC ( G ) \operatorname{QEC}(G) QEC ( G ) is the conditional maximum of ⟨ f , D f ⟩ \langle f,Df\rangle ⟨ f , D f ⟩ subject to
⟨ f , f ⟩ = f 0 2 + ∑ i = 1 p ⟨ f i , f i ⟩ = 1 , ⟨ 1 , f ⟩ = f 0 + ∑ i = 1 p ⟨ 1 , f i ⟩ = 0. (64) \langle f,f\rangle=f_0^2+\sum_{i=1}^{p}\langle f_i,f_i\rangle=1,\qquad\langle1,f\rangle=f_0+\sum_{i=1}^{p}\langle1,f_i\rangle=0. \tag*{(64)} ⟨ f , f ⟩ = f 0 2 + i = 1 ∑ p ⟨ f i , f i ⟩ = 1 , ⟨ 1 , f ⟩ = f 0 + i = 1 ∑ p ⟨ 1 , f i ⟩ = 0. (64)
After simple algebra using (A.3) we come to
⟨ f , D f ⟩ = − ∑ i = 1 p ( ⟨ f i , f i ⟩ + ⟨ 1 , f i ⟩ 2 ) (65) \langle f,Df\rangle=-\sum_{i=1}^{p}\left(\langle f_i,f_i\rangle+\langle1,f_i\rangle^2\right) \tag*{(65)} ⟨ f , D f ⟩ = − i = 1 ∑ p ( ⟨ f i , f i ⟩ + ⟨ 1 , f i ⟩ 2 ) (65)
In this connection we recall the following
Lemma A.1 ([26 ] ). Notations and assumptions being as above, let a i > 0 a_i>0 a i > 0 for i = 1 , 2 , … , p i=1,2,\ldots,p i = 1 , 2 , … , p . The conditional minimum of the quadratic function
∑ i = 1 p a i ( ⟨ f i , f i ⟩ + ⟨ 1 , f i ⟩ 2 ) \sum_{i=1}^{p}a_i\left(\langle f_i,f_i\rangle+\langle1,f_i\rangle^2\right) i = 1 ∑ p a i ( ⟨ f i , f i ⟩ + ⟨ 1 , f i ⟩ 2 ) subject to (A.3) coincides with the minimal solution to
∑ i = 1 p n i a i n i + a i − λ = 1 λ . \sum_{i=1}^{p}\frac{n_i}{a_i n_i+a_i-\lambda}=\frac{1}{\lambda}. i = 1 ∑ p a i n i + a i − λ n i = λ 1 .
Then we have
Theorem A.2. Let p ≥ 1 p\geq1 p ≥ 1 and n 1 ≥ 1 , … , n p ≥ 1 n_1\geq1,\ldots,n_p\geq1 n 1 ≥ 1 , … , n p ≥ 1 . Let λ ∗ \lambda^* λ ∗ be the minimal solution to
∑ i = 1 p n i n i + 1 − λ = 1 λ . \sum_{i=1}^{p}\frac{n_i}{n_i+1-\lambda}=\frac{1}{\lambda}. i = 1 ∑ p n i + 1 − λ n i = λ 1 . Then we have
QEC ( K n 1 + 1 ⋆ K n 2 + 1 ⋆ ⋯ ⋆ K n p + 1 ) = − λ ∗ . \operatorname{QEC}(K_{n_1+1}\star K_{n_2+1}\star\cdots\star K_{n_p+1})=-\lambda^*. QEC ( K n 1 + 1 ⋆ K n 2 + 1 ⋆ ⋯ ⋆ K n p + 1 ) = − λ ∗ .
Proof. By direct application of Lemma A.1 to (A.4).
Theorem A.3. For m ≥ 2 m\geq2 m ≥ 2 and n ≥ 2 n\geq2 n ≥ 2 we have
QEC ( K m ⋆ K n ) = − m n m n + m n ( m − 1 ) ( n − 1 ) . \operatorname{QEC}(K_m\star K_n)=-\frac{mn}{mn+\sqrt{mn(m-1)(n-1)}}. QEC ( K m ⋆ K n ) = − mn + mn ( m − 1 ) ( n − 1 ) mn .
Proof. Straightforward by setting n 1 = m − 1 n_1=m-1 n 1 = m − 1 and n 2 = n − 1 n_2=n-1 n 2 = n − 1 in Theorem A.2.
Theorem A.4. Let p ≥ 1 p \ge1 p ≥ 1 and n ≥ 2 n \ge2 n ≥ 2 . Then for the p p p -fold star power K n ⋆ p = K n ⋆ ⋯ ⋆ K n K_n^{\star p}=K_n\star\cdots\star K_n K n ⋆ p = K n ⋆ ⋯ ⋆ K n (p p p times) we have
QEC ( K n ⋆ p ) = − n p ( n − 1 ) + 1 . \operatorname{QEC}(K_n^{\star p})=-\frac{n}{p(n-1)+1}. QEC ( K n ⋆ p ) = − p ( n − 1 ) + 1 n .
Proof. Straightforward by setting n i = n − 1 n_i=n-1 n i = n − 1 in Theorem A.2.