Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Graph Entropy Based on Strong Coloring of Uniform Hypergraphs

Graph Entropy Based on Strong Coloring of Uniform Hypergraphs axioms Article Graph Entropy Based on Strong Coloring of Uniform Hypergraphs 1,2 1,2,3 2,3,4, 1 Lusheng Fang , Bo Deng , Haixing Zhao * and Xiaoyun Lv School of Mathematics and Statistics, Qinghai Normal University, Xining 810001, China; lusheng_fang@126.com (L.F.); dengbo450@163.com (B.D.); lxy09062021@126.com (X.L.) The State Key Laboratory of Tibetan Information Processing and Application, Xining 810008, China School of Computer, Qinghai Normal University, Xining 810008, China Academy of Plateau, Science and Sustainability, Xining 810008, China * Correspondence: h.x.zhao@163.com Abstract: The classical graph entropy based on the vertex coloring proposed by Mowshowitz depends on a graph. In fact, a hypergraph, as a generalization of a graph, can express complex and high-order relations such that it is often used to model complex systems. Being different from the classical graph entropy, we extend this concept to a hypergraph. Then, we define the graph entropy based on the vertex strong coloring of a hypergraph. Moreover, some tightly upper and lower bounds of such graph entropies as well as the corresponding extremal hypergraphs are obtained. Keywords: hypergraph; graph entropy; strong coloring 1. Introduction Hypergraphs are an important generalization of ordinary graphs. In this paper, some problems on extremal values of graph entropy based on the strong coloring in k-uniform hypergraphs are studied. Indeed, the colorings for hypergraphs are also a natural extension of colorings for graphs, which have various applications (timetabling Citation: Fang, L.; Deng, B.; Zhao, H.; and scheduling problems, planning of experiments, multi-user source coding, etc.) and Lv, X. Graph Entropy Based on Strong offer rich connections with other combinatorial areas (probabilistic methods, extremal set Coloring of Uniform Hypergraphs. theory, Ramsey theory, discrepancy theory, etc.). Axioms 2022, 11, 3. https://doi.org/ In information theory, Shannon s entropy, as a well-known information entropy, was 10.3390/axioms11010003 proposed by Shannon [1]. As one of the most important indicators in information theory, Academic Editor: Elena Guardo it can measure the unpredictability of information contents. Let p = f p , p , , p g be a 1 2 probability distribution, where p = 1 and 0  p  1. Shannon s entropy is defined as i i i=1 Received: 22 November 2021 Accepted: 18 December 2021 Published: 22 December 2021 I( p) = ( p log p ). i i i=1 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in 0 Combining Shannon s entropy with the probability distribution defined on the vertex published maps and institutional affil- set or edge set of a graph, the graph entropy is obtained. Indeed, graph entropy plays an iations. important role in many disciplines such as information theory, biology, chemistry and sociology. It can not only express the structure information contents of a graph but also serve as a complexity measure. Up until now, many graph entropies have been proposed in [2–14]. For more results on the theory and applications of graph entropies, we refer the Copyright: © 2021 by the authors. reader to [10,13,15–17]. Licensee MDPI, Basel, Switzerland. In view of the vast amount of existing graph entropies of ordinary graphs, there is This article is an open access article little work on graph entropy of hypergraphs [18,19]. Inspired by Mowshowitz [6], who distributed under the terms and introduced a graph entropy based on the vertex coloring, we define a graph entropy (see conditions of the Creative Commons Definition 1) based on the strong coloring in a hypergraph. Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ A hypergraph H = (V, E) with n vertices and m edges consists of a set of vertices 4.0/). V = fv , v , , v g and a set of edges E = fe , e , e g, which is a family of subsets of 1 2 n 1 2 m Axioms 2022, 11, 3. https://doi.org/10.3390/axioms11010003 https://www.mdpi.com/journal/axioms Axioms 2022, 11, 3 2 of 9 V such that e 6= Æ (i = 1, 2, , m) and [ e = V. A hypergraph in which all edges have i i the same cardinality k is called k-uniform. A k-uniform hypergraph H is called simple if there are no multiple edges in H, that is, all edges in H are distinct. All hypergraphs considered here are simple and k-uniform with k  3. For a k-uniform hypergraph H = (V, E), the degree d of a vertex v 2 V is defined as d = je : v 2 e 2 Ej. A vertex of degree one v v i i is called a pendent vertex. Otherwise, it is called a non-pendent vertex. An edge e 2 E is called a pendent edge if e contains exactly k 1 pendent vertices. Otherwise, it is called a non-pendent edge. A walk W of length l in H is a sequence of alternating vertices and edges, i.e., v e v e  e v , where fv , v g  e for i = 1, , l. If v = v , then W is 0 1 1 2 l l i1 i i 0 l called a circuit. A walk of H is called a path if no vertices and edges are repeated. A circuit H is called a cycle if no vertices and edges are repeated except v = v . A distance d(x, y) 0 l between two vertices x and y is the minimum length of a path which connects x and y. The diameter d( H) of H = (V, E) is defined by d( H) = maxfd(x, y) j x, y 2 Vg. In [20–22], more hypergraph concepts are introduced. Let H = (V, E) be a hypergraph with vertex coloring. A strong k-coloring of H is a partition (V , V , , V ) of V such that the same color does not appear twice in the 1 k same edge. In other words, je\ Vj  1 for any edge and any element of the partition. If a partition (V , V , , V ) of V is a strong k-coloring of H, it is said to be a chromatic 1 2 k decomposition of H. Then set V is called a color classe for 1  i  k. The strong chromatic number c( H) is the smallest number k such that H has a strong k-coloring. Define the non-increasing chromatic decomposition sequence of H by p ( H) = ( V , V , , V ) for a j j j j j j c 1 2 chromatic decomposition denoted by c, that is, jV j  jV j    jV j. 1 2 k Definition 1. Let H = (V, E) be a hypergraph with n vertices and m edges. Let V = fVg is an arbitrary chromatic decomposition of H and c( H) = c. Then the graph entropy based on the vertex strong coloring I ( H) of H is given by jVj jVj i i I ( H) = minf log g c å ˆ n n i=1 = log n maxf jVj logjVjg. (1) å i i ˆ n i=1 h( H) If h( H) = max å jVj logjVj, then I ( H) = log n . i i i=1 n The paper is organized as follows. In Section 2, some concepts and existing results on hypergraphs are given. In Section 3, the extremal properties of graph entropies are studied. The paper finishes with a conclusion in Section 4. 2. Preliminaries In this section, some basic definitions and results are given. Definition 2 ([19]). Let H be a k-uniform hypergraph with n vertices, m edges and l connected components. The cyclomatic number of H is denoted and defined by c( H) = m(k 1) n + l. The hypergraph H is called a c(G)-cyclic hypergraph. A connected hypergraph H does not contain any cycles if and only if c( H) = 0. Definition 3 ([23]). Let G = (V, E) be an ordinary graph. For an integer k  3, the k-th power k k k of G, denoted by G := (V , E ), is defined as the k-uniform hypergraph with the set of vertices k k V = V [ ([ fi , , i g) and the set of edges E = fe[fi , , i gje 2 Eg, e2E e,1 e,k2 e,1 e,k2 where i , , i are new added vertices for e. e,1 e,k2 Axioms 2022, 11, 3 3 of 9 Definition 4 ([23]). The k-th power of S , denoted by S , is called a hyperstar (see Figure 1 for an example). Figure 1. Hyperstar S . Definition 5 ([20]). Let H = (V, E) be a hypergraph. The 2-section of H is the graph, denoted by [ H] , where vertices are the vertices of H and where two distinct vertices form an edge if and only if they are in the same edge of H. An example of 2-section is given in Figure 2. Figure 2. A 2-section of a hypergraph. Lemma 1 ([20]). The strong chromatic number denoted by c( H) is the smallest k such that H has a strong k-coloring. Then c( H) is the chromatic number of the graph [ H] . Definition 6 ([24]). A graph G with vertex coloring is called color-critical if c(G ) < c(G) for every proper subgraph G of G. If G is a color-critical k-chromatic graph, then G is called critically k-chromatic or simply k-critical. Lemma 2 ([24]). Every k-critical graph, k  2, is (k 1)-edge-connected. Definition 7. A k-uniform hypergraph H with vertex coloring is called color-critical if c( H ) < c( H) for every k-uniform proper subhypergraph H of H. If H is color-critical and k-chromatic, then H is called critically k-chromatic or simply k-critical. Some operations [25] of moving edges for hypergraphs are stated as follows. Definition 8. Let r  1 and H = (V, E) be a hypergraph with u 2 V and e , , e 2 E such 1 r that u 2 / e for i = 1, , r. Suppose that v 2 e and write e = (enfv g)[fug(i = 1, , r). i i i i 0 0 0 0 0 0 Let H = (V, E ) be the hypergraph with E = (Enfe , , e g)[fe , , e g. Then H is said i r 1 r to be obtained from H by moving edge (e , , e ) from (v , , v ) to u. r r 1 1 Lemma 3. Let k-uniform hypergraph H be t-critical (t > k). The graph [ H] is obtained from 0 0 [ H] by deleting the vertex whose degree is k 1. Then c([ H] ) = c( H) and [ H] is t-critical. 2 2 Proof. By Lemma 1, we have c([ H] ) = t. By contradiction, suppose c([ H] ) < t. If 0 0 k 1 < c([ H] ) < t, then c([ H] ) = c([ H] ), which contradicts with c( H) = t. If 2 2 Axioms 2022, 11, 3 4 of 9 0 0 c([ H] ) < k 1, then c([ H] )  c([ H] ) + 1, which contradicts with c( H) = t. Thus, 2 2 c([ H] ) = t. 0 0 Now, we prove that [ H] is t-critical. Assume [ H] is not t-critical. Then there is a 2 2 00 0 00 0 proper subgraph [ H] of [ H] such that c([ H] ) = t. Any proper subgraph of [ H] can be 2 2 2 2 obtained by deleting vertices whose degree is k 1 from the 2-section of the hypersubgraph 0 0 00 of hypergraph H. Then, there is a hypersubgraph H of H with c( H ) = c([ H] ) = t, which implies that H is not t-critical and this is a contradiction. Hence, [ H] is t-critical. 3. Extremality of I ( H) among k-Uniform (k  3) Hypergraphs In this section, we investigate the extremality of graph entropy based on the vertex strong coloring among all k-uniform (k  3) supertrees and k-uniform c( H)-cyclic hyper- graphs (k  c( H) + 2, c( H)  1). Assume X = ffx , , x gjx    x , x = 1 n 1 n i i=1 + + N , x 2 Z (1  i  n, N 2 Z )g. 0 i 0 Lemma 4. Suppose f (X) = x logx , where X = fx , , x g 2 X. For any x , x 2 X, if i i 1 n i j i=1 x x = 0 or x x = 1, then f (X) obtains the minimal value. i j i j (1) (1) Proof. Suppose N is divisible by n. Assume X 2 X and X = fx , , x g. For any 0 1 1 n (1) (1) (1) (1) (2) (2) x , x 2 X , it has x x = 0. Suppose X 2 X and X 6= X = fx , , x g. 1 2 1 2 n i j i j 1 (2) (2) (2) (2) (2) (2) Then there are x , x 2 X , where x x  2. Let X 2 X and X = fx , , x 2 3 3 i j j i 1 j (2) (2) 1, , x + 1, , x g. Then (2) (2) (2) (2) (2) (2) f (X ) f (X ) = x logx + x logx (x + 1)log(x + 1) 2 3 i i j j i i (2) (2) (x 1)log(x 1) j j (2) (2) (2) (2) = x logx (x 1)log(x 1) j j j j (2) (2) (2) (2) (x + 1)log(x + 1) x logx i i i i 1 1 = (logx + ) (logx + ) ln2 ln2 > 0, (2) (2) (2) (2) where x 2 (x 1, x ) and x 2 (x , x + 1). So, we obtain f (X ) > f (X ). This 1 2 2 3 j j i i implies that f (X) attains the minimum value as X = X . For the case that N is not divisible by n, with the same way as above, we can check that (4) (4) (4) f (X) attains the minimum value as X = X , where X 2 X and X = fx , x  , x g 4 4 4 n 1 2 (4) (4) (4) (4) satisfying x x = 1 or x x = 0 for 1  i, j  n. i j i j Lemma 5. Let H = (V, E) be a k-uniform hypergraph on n vertices with m > 2 edges and max d(v) = 2. Then the number of vertices whose degree is 1 in hypergraph is n m + l c( H) v2V nm+lc( H) and hypergraph H has, at most, b c pendent edges. k1 Proof. Suppose the number of vertices whose degree is 1 in hypergraph H is t, then hypergraph H has, at most,b c pendent edges. Let the number of vertices whose degree k1 is 2 in hypergraph is x. By c( H) = m(k 1) n + l and å d = km, we have i=1 km = 2x + (n x), x = m l + c( H). So, the number of vertices whose degree is 1 in hypergraph is n m + l c( H) and nm+lc( H) hypergraph H has, at most, b c pendent edges. k1 Axioms 2022, 11, 3 5 of 9 Lemma 6. Let H = (V, E) be a k-uniform hypergraph (k  3) on n vertices with m edges and l = 1 connected components. If k  c( H) + 2, then c( H) = k. Proof. By contradiction, suppose c( H) > k as k  c( H) + 2. If c( H) is k + 1, then there 0 0 0 exists a subhypergraph H of H, which is (k + 1)-critical. Let V = fv , , v g  V( H ) 1 k+1 such that v is colored with color i. Now, we discuss the following two cases. 0 0 0 Case 1. There is a vertex set V in H such that any two vertices in V are in the same edge. 0 0 0 Let H = (V , E ) be a k-uniform hypergraph of n vertices and m edges, with l = 1 0 0 H H 0 0 connected component. Since hypergraph H is k uniform, all vertices of V cannot appear 0 0 in one edge of H . By the condition that any two vertices in vertex set V are in the same edge, there are three vertices in V to form a circle of length 3. Such a cycle is denoted by 0 0 c = v e v e v e v , where e , e , e 2 E 0 and v , v , v 2 V . For any v 2 V nfv , v , v g, 1 1 1 2 2 3 3 1 1 2 3 1 2 3 i 1 2 3 we find that there are two vertices of fv , v , v g such that the two vertices and the vertex 2 3 v can form a cycle of length 3. Assume v and v are such two vertices and the cycle is i 2 3 c = v e v e v e v , where e 2 E 0 is an edge containing v and v , and e 2 E 0 is an i 2 2 3 j i i 2 i i 2 j H H edge containing v and v . If there is not such a cycle c , then the vertices v , v , v and v i 3 i 1 2 3 i must be in the same edge, which is a contradiction with c . So, there must be a cycle c in 1 i hypergraph H for 4  i  k + 1. 0 0 0 00 Let H be the graph obtained from adding the isolated vertices v , , v . Let H be 0 1 k1 the k-uniform hypergraph obtained from H by the following operations of moving edges, S S 0 0 0 0 i.e., e = (e nfv g) fv g and e = (e nfv g) fv g (i = 4, , k + 1). Then, we see 1 1 i i 1 1 i i2 that H is connected and it has no cycles c , c  c . Thus, 1 4 k+1 00 0 0 c( H ) = m (k 1) [n + k 1] + 1, 0 00 0 n + c( H ) = m (k 1) k + 2 and 0 0 n  m (k 1) k + 2. (2) 0 0 0 From c( H ) = m (k 1) n + 1 and Inequality (2), we have 0 0 0 c( H ) = m (k 1) n + 1 0 0 m (k 1) [m (k 1) k + 2] + 1 = k 1  c( H) + 1  c( H ) + 1. 0 0 Then, we obtain that c( H )  c( H ) + 1, which is a contradiction. Case 2. There are at least two vertices in V which are not in the same edge for any 0 0 vertex set V in H . 0 0 0 Let [ H ] be the graph obtained from [ H ] by deleting the vertex whose degree is 0 0 0 0 0 k 1. By Lemma 3, we obtain that c([ H ] ) = c( H ) and [ H ] is (k + 1)-critical. By the 2 2 condition, there are at least two vertices in V which are not in the same edge for any 0 0 0 vertex set V in H , there are at least two vertices in V that are not adjacent. Suppose v is 0 0 0 0 0 not adjacent to v , where v , v 2 V . By Lemma 2, [ H ] is k-edge-connected. Then [ H ] j i j 2 2 contains k pairwise edge-disjoint v v paths. So, H contains k pairwise edge-disjoint j i 0 0 v v paths. Let P , , P be k pairwise edge-disjoint v v paths in H . Let H be the j i 1 k j i 0 0 graph obtained from adding k 1 isolated vertices v , , v . Suppose P contains an 1 k1 edge e and a vertex u such that u 2 e and u 6= v , v , where 1  i  k 1. Let H be the i i i i i i j k-uniform hypergraph obtained from H by the following operations of moving edges, i.e., 0 Axioms 2022, 11, 3 6 of 9 0 0 00 e = (e nfu g) fv g (i = 1, , k 1). Then, we see that H is connected and it has no i i i i paths P , P . Thus, 1 k1 00 0 0 c( H ) = m (k 1) [n + k 1] + 1, 0 00 0 n + c( H ) = m (k 1) k + 2 and 0 0 n  m (k 1) k + 2. (3) 0 0 0 From c( H ) = m (k 1) n + 1 and Inequality (3), we have 0 0 0 c( H ) = m (k 1) n + 1 0 0 m (k 1) [m (k 1) k + 2] + 1 = k 1  c( H) + 1  c( H ) + 1. 0 0 Then we obtain that c( H )  c( H ) + 1, which is a contradiction. For the upper bound about I ( H), due to the lack of effective analysis methods, we only consider k-uniform hypergraph H = (V, E) on n vertices with m > 2 edges, where m nm+1c( H) 2 2 (2 c( H))k + (k 1) c( H) and is an integer. (2 c( H))k + (k 1) c( H) k1 is the maximum number of edges when the diameter of H is less than or equal to 5, where H is a k-uniform hypergraph on n vertices with m edges and the maximum degree 2. Theorem 1. Let H = (V, E) be a k-uniform hypergraph (k  c( H) + 2) on n vertices with nm+1c( H) m > 2 edges, where is an integer and m  (2 c( H))k + (k 1) c( H). Then k1 n n n n h( H)  r(b c + 1) log(b c + 1) + (k r)b c logb c k k k k with the equality holding if and only if p ( H) = p ( H ), where r = nb ck and H is a c c 1 1 k-uniform hypergraph with the maximum degree 2, possessing n vertices and m edges, which has 0 0 nm+1c( H) pendent edges. Then, we see that there is a hypersubgraph H of H with c( H ) = k1 c( H) = c( H ), where the hypergraph H is obtained from jointing two edges by c( H) + 1 common vertices (see Figure 3). Figure 3. The k-uniform c( H)-cyclic hypersubgraph H of H . nm+1c( H) Proof. By Lemma 6, c( H) = k. By Lemma 5, and is an integer, the hypergraph k1 nm+1c( H) H has, at most, pendent edges. For H on n vertices with m > 2 edges and the 1 1 k1 maximum degree 2, there is H that satisfies that the diameter of H is less than or equal to 1 1 5 because of m  (2 c( H))k + (k 1) c( H). By the structure and strong coloring of hypergraph H , the chromatic decomposition sequences obtained from all strong coloring nm+1c( H) of k-uniform hypergraph H are the same and unique when is an integer k1 and d( H )  5 , which is supposed to be p ( H ) = fjV j, ,jV jg. If n is divisible by 1 1 1 k k, then V =  = V in the case of H . Otherwise, V =  = V = b c + 1, j j j j j j j j 1 1 1 r n n n n jV j =  = jV j = b c, where r = nb ck. Thus, h( H ) = r(b c + 1) log(b c + 1) + r+1 k 1 k k k k n n (k r)b c logb c. In addition, jVj V  2 does not hold for any jVj, V 2 p ( H ). c 1 i j i j k k By Lemma 4, there is no such hypergraph H satisfying h( H) < h( H ). This completes the proof. Axioms 2022, 11, 3 7 of 9 From Theorem 1 and Equality (1), we have the following result. Theorem 2. Let H = (V, E) be a k-uniform hypergraph (k  c( H) + 2) on n vertices with nm+1c( H) m > 2 edges, where is an integer and m  (2 c( H))k + (k 1) c( H). Then k1 n n n n r(b c + 1) log(b c + 1) + (k r)b c logb c k k k k I ( H)  log n , the equality holds if and only if p ( H) = p ( H ), where H are given in Theorem 1. c c 1 1 From Theorem 2 and Equality (1), we have the following result. Corollary 1. Let H = (V, E) be a k-uniform (k  3) supertree on n vertices with m > 2 edges, nm+1 2 where is an integer and m  2k + (k 1) . Then k1 n n n n r(b c + 1) log(b c + 1) + (k r)b c logb c k k k k I ( H)  log n with the equality holding if and only if p ( H) = p ( H ), where n = b ck + r (0  r  k 1) c c and H is a k-uniform supertree with the maximum degree 2, possessing n vertices and m edges, nm+1 which has pendent edges. k1 Theorem 3. Let H = (V, E) be a k-uniform hypergraph (k  c( H) + 2) on n vertices with m > 2 edges. Then h( H)  (k 2)m log m + (m c( H)) log(m c( H)) with the equality holding if and only if p ( H) = p ( H ), where the hypergraph H is obtained c c 2 2 from jointing c( H) + 1 edges with two common vertices u and v and jointing m c( H) 1 edges by the vertex v, respectively. (see Figure 4) Figure 4. The k-uniform c( H)-cyclic hypergraph H . Proof. By Lemma 6, c( H) = k. According to the structure and the strong coloring of a hypergraph, the chromatic decomposition sequence obtained from any strong col- oring of H is the same and unique, which is denoted by p ( H ) = fjV j, ,jV jg. 2 c 2 1 k Then jV j =  = jV j = m , jV j = m c( H ) and jV j = 1. So h( H ) = 1 k2 k1 2 k 2 (k 2)m log m + (m c( H )) log(m c( H )). Note that 1  V  m for any strong j j 2 2 i coloring of a hypergraph. For any jVj  V , we see that jVj = 1 or V = m. Sup- i j i j pose there is a hypergraph H = (V, E) with c( H) = c( H ) and its coloring c satisfying 0 0 0 0 h ( H) = h( H). Let p ( H) = V , , V 6= p ( H ). Then there is V  V sat- c c c 1 k i j 0 0 T isfying V < m and V > 1. So, there are e and e satisfying e e 6= Æ. Moreover, 2 2 1 1 j i there is a vertex v 2 e and a vertex v 2 e satisfying v , v 2 V . Suppose u 2 e e , 1 1 2 2 1 2 1 2 i Axioms 2022, 11, 3 8 of 9 then d(u) > 1 and u 2 V . Let e , , e be the other edges of H containing v . Let 3 r 2 H = (V 0 , E 0 ) be a k-uniform hypergraph obtained from H by following operations H H 0 S 0 S of moving edges, i.e., e = (e nfug) fv g and e = (e nfv g) fv g (i = 3, , r). 2 1 i 2 1 Obviously, H is also a k-uniform c( H)-cyclic hypergraph. Then, color the vertex v with the color j noting that its color is i before. Thus, there is a coloring c in H satisfying n o 0 0 0 0 0 p ( H ) = V , , V + 1, , V 1, , V . Then 1 j i k 0 0 0 0 0 h( H) h ( H ) = V log V + V log V 1 j j i i 0 0 0 0 ( V + 1)log( V + 1) ( V 1)log( V 1) j j i i h i 0 0 0 0 = V log V ( V 1)log( V 1) i i i i h i 0 0 0 0 ( V + 1)log( V + 1) V log V j j j j 1 1 = (logx + ) (logx + ) ln2 ln2 < 0, 0 0 0 0 0 0 where x 2 ( V 1, V ) and x 2 ( V , V + 1). That is, h( H) < h ( H )  h( H ), 1 2 i i j j 1 which means that h( H) attains the maximum value as p( H) = p( H ). From Theorem 3 and Equality (1), we have the following result. Theorem 4. Let H = (V, E) be a k-uniform hypergraph (k  c( H) + 2) on n vertices with m > 2 edges. Then (k 2)m log m + (m c( H)) log(m c( H)) log n  I ( H), the equality holds if and only if p ( H) = p ( H ), where H are given in Theorem 3. c c 2 2 From Theorem 4 and Equality (1), we have the following result. Corollary 2. Let H = (V, E) be a k-uniform (k  3) supertree on n vertices with m edges. Then (k 1)m log m log n  I ( H). The equality holds if and only if p ( H) = p (S ). c c m+1 4. Conclusions In this paper, we determine the extremal values for graph entropy based on strong coloring for k-uniform hypergraph H. For k-uniform hypergraph H (k  c( H) + 2) with nm+1c( H) n vertices and m edges, when is an integer and m  (2 c( H))k + (k 1) k1 c( H), we obtain an upper bound of the graph entropy based on strong coloring by using n and k. For k-uniform hypergraph H (k  c( H) + 2) with n vertices and m edges, we obtain a lower bound of graph entropy based on strong coloring by using n, k, m and c( H). Hypergraph is a generalization of a graph. However, there is little research on the entropy of a hypergraph. So, it is meaningful to extend the conclusions of graph entropies based on graphs to hypergraphs in the future. Author Contributions: Conceptualization, methodology, software, software, validation, writing— original draft preparation, L.F.; formal analysis, writing—review and editing, B.D.; supervision, H.Z.; project administration, X.L. All authors have read and agreed to the published version of the manuscript. Axioms 2022, 11, 3 9 of 9 Funding: This research was funded by the Key Laboratory of Tibetan Information Processing Min- istry of Education, Tibetan Information Processing Engineering Technology and Research Center of Qinghai Province, Qinghai-Tibet Plateau Innovation and Talent Introduction Base in Big Data Subject of Language and Culture (Grant No. 111Project D20035), Qinghai Office of Science and Technology (Grant No. 2019-ZJ-7086). Data Availability Statement: Not applicable. Acknowledgments: The authors were very grateful to the referees and the editor for their valuable comments and suggestions, which significantly improved the presentation of this manuscript. Conflicts of Interest: The authors declare no conflict of interest. References 1. Shannon, C.E.; Weaver, W. The Mathematical Theory of Communication; University of Illinois Press: Urbana, IL, USA, 1949. 2. Rashevsky, N. Life, information theory and topology. Bull. Math. Biophys. 1955, 17, 229–235. [CrossRef] 3. Mowshowitz, A. Entropy and the complexity of graphs: I. An index of the relative complexity of a graph. Bull. Math. Biol. 1968, 30, 175–204. [CrossRef] [PubMed] 4. Mowshowitz, A. Entropy and the complexity of graphs: II. The information content of digraphs and infinite graphs. Bull. Math. Biol. 1968, 30, 225–240. [CrossRef] [PubMed] 5. Mowshowitz, A. Entropy and the complexity of graphs: III. Graphs with prescribed information content. Bull. Math. Biol. 1968, 30, 387–414. [CrossRef] 6. Mowshowitz, A. Entropy and the complexity of graphs: IV. Entropy measures and graphical structure. Bull. Math. Biol. 1968, 30, 533–546. [CrossRef] 7. K’orner, J. Coding of an information source having ambiguous alphabet and the entropy of graphs. In Proceedings of the 6th Prague Conference on Information Theory, Prague, Czech Republic, 19–25 September 1973; pp. 411–425. 8. Dehmer, M. Information processing in complex networks: Graph entropy and information functionals. Appl. Math. Comput. 2008, 201, 82–94. [CrossRef] 9. Bonchev, D. Information Theoretic Indices for Characterization of Chemical Structures; Research Studies Press: Chichester, UK, 1983. 10. Dehmer, M.; Mowshowitz, A. A history of graph entropy measures. Inf. Sci. 2011, 181, 57–78. [CrossRef] 11. K’orner, J.; Marton, K. Graphs that split entropies. SIAM J. Discret. Math. 1988, 1, 71–79. [CrossRef] 12. Li, X.; Qin, Z.; Wei, M.; Gutman, I.; Dehmer, M. Novel inequalities for generalized graph entropies–Graph energies and topological indices. Appl. Math. Comput. 2015, 259, 470–479. [CrossRef] 13. Simonyi, G. Perfect graphs and graph entropy, An updated survey. In Perfect Graphs; Ramirez-Alfonsin, J., Reed, B., Eds.; John Wiley & Sons: Hoboken, NJ, USA, 2001; pp. 293–328. 14. Trucco, E. A note on the information content of graphs. Bull. Math. Biol. 1956, 18, 129–135. [CrossRef] 15. Li, X.; Wei, M. Graph entropy: Recent results and perspectives. In Mathematical Foundations and Applications of Graph Entropy; Dehmer, M., Ed.; Wiley-VCH Verlag: Weinheim, Germany, 2016; pp. 133–182. 16. Simonyi, G. Graph entropy: A survey. Comb. Optim. 1995, 20, 399–441. 17. Cao, S.; Dehmer, M.; Shi, Y. Extremality of degree-based graph entropies. Inf. Sci. 2014, 278, 22–33. [CrossRef] 18. Hu, D.; Li, X.L.; Liu, X.G.; Zhang, S.G. Extremality of Graph Entropy Based on Degrees of Uniform Hypergraphs with Few Edges. Acta Math. Sin. 2019, 35, 1238–1250. [CrossRef] 19. Fan, Y.-Z.; Liu, A.-H.; Peng, X.-X.; Tan, Y.-Y. Maximizing spectral radii of uniform hypergraphs with few edges. Discuss. Math. Graph Theory 2016, 36, 845. [CrossRef] 20. Bretto, A. Hypergraph Theory; Springer: Berlin/Heidelberg, Germany, 2013. 21. Berge, C. Hypergraphs; North-Holland: Amsterdam, The Netherlands, 1989. 22. Gionfriddo, M.; Milazzo, L.; Voloshin, V. Hypergraphs and Designs; Nova Publishers: New York, NY, USA, 2015. 23. Hu, S.; Qi, L.; Shao, J.-Y. Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues. Linear Algebra Its Appl. 2013, 439, 2980–2998. [CrossRef] 24. Chartrand, G.; Lesniak, L.; Zhang, P. Graphs and Digraphs; Brooks/Cole Pub. Co.: Pacific Grove, CA, USA, 2011. 25. Li, H.; Shao, J.-Y.; Qi, L. The extremal spectral radii of k -uniform supertrees. J. Comb. Optim. 2015, 32, 741–764. [CrossRef] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Axioms Multidisciplinary Digital Publishing Institute

Graph Entropy Based on Strong Coloring of Uniform Hypergraphs

Fang, Lusheng; Deng, Bo; Zhao, Haixing; Lv, Xiaoyun
Axioms , Volume 11 (1) – Dec 22, 2021
Download PDF
9 pages

Loading next page...
 
/lp/multidisciplinary-digital-publishing-institute/graph-entropy-based-on-strong-coloring-of-uniform-hypergraphs-s06VfjSN90
Publisher
Multidisciplinary Digital Publishing Institute
Copyright
© 1996-2022 MDPI (Basel, Switzerland) unless otherwise stated Disclaimer The statements, opinions and data contained in the journals are solely those of the individual authors and contributors and not of the publisher and the editor(s). MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Terms and Conditions Privacy Policy
ISSN
2075-1680
DOI
10.3390/axioms11010003
Publisher site
See Article on Publisher Site

Abstract

axioms Article Graph Entropy Based on Strong Coloring of Uniform Hypergraphs 1,2 1,2,3 2,3,4, 1 Lusheng Fang , Bo Deng , Haixing Zhao * and Xiaoyun Lv School of Mathematics and Statistics, Qinghai Normal University, Xining 810001, China; lusheng_fang@126.com (L.F.); dengbo450@163.com (B.D.); lxy09062021@126.com (X.L.) The State Key Laboratory of Tibetan Information Processing and Application, Xining 810008, China School of Computer, Qinghai Normal University, Xining 810008, China Academy of Plateau, Science and Sustainability, Xining 810008, China * Correspondence: h.x.zhao@163.com Abstract: The classical graph entropy based on the vertex coloring proposed by Mowshowitz depends on a graph. In fact, a hypergraph, as a generalization of a graph, can express complex and high-order relations such that it is often used to model complex systems. Being different from the classical graph entropy, we extend this concept to a hypergraph. Then, we define the graph entropy based on the vertex strong coloring of a hypergraph. Moreover, some tightly upper and lower bounds of such graph entropies as well as the corresponding extremal hypergraphs are obtained. Keywords: hypergraph; graph entropy; strong coloring 1. Introduction Hypergraphs are an important generalization of ordinary graphs. In this paper, some problems on extremal values of graph entropy based on the strong coloring in k-uniform hypergraphs are studied. Indeed, the colorings for hypergraphs are also a natural extension of colorings for graphs, which have various applications (timetabling Citation: Fang, L.; Deng, B.; Zhao, H.; and scheduling problems, planning of experiments, multi-user source coding, etc.) and Lv, X. Graph Entropy Based on Strong offer rich connections with other combinatorial areas (probabilistic methods, extremal set Coloring of Uniform Hypergraphs. theory, Ramsey theory, discrepancy theory, etc.). Axioms 2022, 11, 3. https://doi.org/ In information theory, Shannon s entropy, as a well-known information entropy, was 10.3390/axioms11010003 proposed by Shannon [1]. As one of the most important indicators in information theory, Academic Editor: Elena Guardo it can measure the unpredictability of information contents. Let p = f p , p , , p g be a 1 2 probability distribution, where p = 1 and 0  p  1. Shannon s entropy is defined as i i i=1 Received: 22 November 2021 Accepted: 18 December 2021 Published: 22 December 2021 I( p) = ( p log p ). i i i=1 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in 0 Combining Shannon s entropy with the probability distribution defined on the vertex published maps and institutional affil- set or edge set of a graph, the graph entropy is obtained. Indeed, graph entropy plays an iations. important role in many disciplines such as information theory, biology, chemistry and sociology. It can not only express the structure information contents of a graph but also serve as a complexity measure. Up until now, many graph entropies have been proposed in [2–14]. For more results on the theory and applications of graph entropies, we refer the Copyright: © 2021 by the authors. reader to [10,13,15–17]. Licensee MDPI, Basel, Switzerland. In view of the vast amount of existing graph entropies of ordinary graphs, there is This article is an open access article little work on graph entropy of hypergraphs [18,19]. Inspired by Mowshowitz [6], who distributed under the terms and introduced a graph entropy based on the vertex coloring, we define a graph entropy (see conditions of the Creative Commons Definition 1) based on the strong coloring in a hypergraph. Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ A hypergraph H = (V, E) with n vertices and m edges consists of a set of vertices 4.0/). V = fv , v , , v g and a set of edges E = fe , e , e g, which is a family of subsets of 1 2 n 1 2 m Axioms 2022, 11, 3. https://doi.org/10.3390/axioms11010003 https://www.mdpi.com/journal/axioms Axioms 2022, 11, 3 2 of 9 V such that e 6= Æ (i = 1, 2, , m) and [ e = V. A hypergraph in which all edges have i i the same cardinality k is called k-uniform. A k-uniform hypergraph H is called simple if there are no multiple edges in H, that is, all edges in H are distinct. All hypergraphs considered here are simple and k-uniform with k  3. For a k-uniform hypergraph H = (V, E), the degree d of a vertex v 2 V is defined as d = je : v 2 e 2 Ej. A vertex of degree one v v i i is called a pendent vertex. Otherwise, it is called a non-pendent vertex. An edge e 2 E is called a pendent edge if e contains exactly k 1 pendent vertices. Otherwise, it is called a non-pendent edge. A walk W of length l in H is a sequence of alternating vertices and edges, i.e., v e v e  e v , where fv , v g  e for i = 1, , l. If v = v , then W is 0 1 1 2 l l i1 i i 0 l called a circuit. A walk of H is called a path if no vertices and edges are repeated. A circuit H is called a cycle if no vertices and edges are repeated except v = v . A distance d(x, y) 0 l between two vertices x and y is the minimum length of a path which connects x and y. The diameter d( H) of H = (V, E) is defined by d( H) = maxfd(x, y) j x, y 2 Vg. In [20–22], more hypergraph concepts are introduced. Let H = (V, E) be a hypergraph with vertex coloring. A strong k-coloring of H is a partition (V , V , , V ) of V such that the same color does not appear twice in the 1 k same edge. In other words, je\ Vj  1 for any edge and any element of the partition. If a partition (V , V , , V ) of V is a strong k-coloring of H, it is said to be a chromatic 1 2 k decomposition of H. Then set V is called a color classe for 1  i  k. The strong chromatic number c( H) is the smallest number k such that H has a strong k-coloring. Define the non-increasing chromatic decomposition sequence of H by p ( H) = ( V , V , , V ) for a j j j j j j c 1 2 chromatic decomposition denoted by c, that is, jV j  jV j    jV j. 1 2 k Definition 1. Let H = (V, E) be a hypergraph with n vertices and m edges. Let V = fVg is an arbitrary chromatic decomposition of H and c( H) = c. Then the graph entropy based on the vertex strong coloring I ( H) of H is given by jVj jVj i i I ( H) = minf log g c å ˆ n n i=1 = log n maxf jVj logjVjg. (1) å i i ˆ n i=1 h( H) If h( H) = max å jVj logjVj, then I ( H) = log n . i i i=1 n The paper is organized as follows. In Section 2, some concepts and existing results on hypergraphs are given. In Section 3, the extremal properties of graph entropies are studied. The paper finishes with a conclusion in Section 4. 2. Preliminaries In this section, some basic definitions and results are given. Definition 2 ([19]). Let H be a k-uniform hypergraph with n vertices, m edges and l connected components. The cyclomatic number of H is denoted and defined by c( H) = m(k 1) n + l. The hypergraph H is called a c(G)-cyclic hypergraph. A connected hypergraph H does not contain any cycles if and only if c( H) = 0. Definition 3 ([23]). Let G = (V, E) be an ordinary graph. For an integer k  3, the k-th power k k k of G, denoted by G := (V , E ), is defined as the k-uniform hypergraph with the set of vertices k k V = V [ ([ fi , , i g) and the set of edges E = fe[fi , , i gje 2 Eg, e2E e,1 e,k2 e,1 e,k2 where i , , i are new added vertices for e. e,1 e,k2 Axioms 2022, 11, 3 3 of 9 Definition 4 ([23]). The k-th power of S , denoted by S , is called a hyperstar (see Figure 1 for an example). Figure 1. Hyperstar S . Definition 5 ([20]). Let H = (V, E) be a hypergraph. The 2-section of H is the graph, denoted by [ H] , where vertices are the vertices of H and where two distinct vertices form an edge if and only if they are in the same edge of H. An example of 2-section is given in Figure 2. Figure 2. A 2-section of a hypergraph. Lemma 1 ([20]). The strong chromatic number denoted by c( H) is the smallest k such that H has a strong k-coloring. Then c( H) is the chromatic number of the graph [ H] . Definition 6 ([24]). A graph G with vertex coloring is called color-critical if c(G ) < c(G) for every proper subgraph G of G. If G is a color-critical k-chromatic graph, then G is called critically k-chromatic or simply k-critical. Lemma 2 ([24]). Every k-critical graph, k  2, is (k 1)-edge-connected. Definition 7. A k-uniform hypergraph H with vertex coloring is called color-critical if c( H ) < c( H) for every k-uniform proper subhypergraph H of H. If H is color-critical and k-chromatic, then H is called critically k-chromatic or simply k-critical. Some operations [25] of moving edges for hypergraphs are stated as follows. Definition 8. Let r  1 and H = (V, E) be a hypergraph with u 2 V and e , , e 2 E such 1 r that u 2 / e for i = 1, , r. Suppose that v 2 e and write e = (enfv g)[fug(i = 1, , r). i i i i 0 0 0 0 0 0 Let H = (V, E ) be the hypergraph with E = (Enfe , , e g)[fe , , e g. Then H is said i r 1 r to be obtained from H by moving edge (e , , e ) from (v , , v ) to u. r r 1 1 Lemma 3. Let k-uniform hypergraph H be t-critical (t > k). The graph [ H] is obtained from 0 0 [ H] by deleting the vertex whose degree is k 1. Then c([ H] ) = c( H) and [ H] is t-critical. 2 2 Proof. By Lemma 1, we have c([ H] ) = t. By contradiction, suppose c([ H] ) < t. If 0 0 k 1 < c([ H] ) < t, then c([ H] ) = c([ H] ), which contradicts with c( H) = t. If 2 2 Axioms 2022, 11, 3 4 of 9 0 0 c([ H] ) < k 1, then c([ H] )  c([ H] ) + 1, which contradicts with c( H) = t. Thus, 2 2 c([ H] ) = t. 0 0 Now, we prove that [ H] is t-critical. Assume [ H] is not t-critical. Then there is a 2 2 00 0 00 0 proper subgraph [ H] of [ H] such that c([ H] ) = t. Any proper subgraph of [ H] can be 2 2 2 2 obtained by deleting vertices whose degree is k 1 from the 2-section of the hypersubgraph 0 0 00 of hypergraph H. Then, there is a hypersubgraph H of H with c( H ) = c([ H] ) = t, which implies that H is not t-critical and this is a contradiction. Hence, [ H] is t-critical. 3. Extremality of I ( H) among k-Uniform (k  3) Hypergraphs In this section, we investigate the extremality of graph entropy based on the vertex strong coloring among all k-uniform (k  3) supertrees and k-uniform c( H)-cyclic hyper- graphs (k  c( H) + 2, c( H)  1). Assume X = ffx , , x gjx    x , x = 1 n 1 n i i=1 + + N , x 2 Z (1  i  n, N 2 Z )g. 0 i 0 Lemma 4. Suppose f (X) = x logx , where X = fx , , x g 2 X. For any x , x 2 X, if i i 1 n i j i=1 x x = 0 or x x = 1, then f (X) obtains the minimal value. i j i j (1) (1) Proof. Suppose N is divisible by n. Assume X 2 X and X = fx , , x g. For any 0 1 1 n (1) (1) (1) (1) (2) (2) x , x 2 X , it has x x = 0. Suppose X 2 X and X 6= X = fx , , x g. 1 2 1 2 n i j i j 1 (2) (2) (2) (2) (2) (2) Then there are x , x 2 X , where x x  2. Let X 2 X and X = fx , , x 2 3 3 i j j i 1 j (2) (2) 1, , x + 1, , x g. Then (2) (2) (2) (2) (2) (2) f (X ) f (X ) = x logx + x logx (x + 1)log(x + 1) 2 3 i i j j i i (2) (2) (x 1)log(x 1) j j (2) (2) (2) (2) = x logx (x 1)log(x 1) j j j j (2) (2) (2) (2) (x + 1)log(x + 1) x logx i i i i 1 1 = (logx + ) (logx + ) ln2 ln2 > 0, (2) (2) (2) (2) where x 2 (x 1, x ) and x 2 (x , x + 1). So, we obtain f (X ) > f (X ). This 1 2 2 3 j j i i implies that f (X) attains the minimum value as X = X . For the case that N is not divisible by n, with the same way as above, we can check that (4) (4) (4) f (X) attains the minimum value as X = X , where X 2 X and X = fx , x  , x g 4 4 4 n 1 2 (4) (4) (4) (4) satisfying x x = 1 or x x = 0 for 1  i, j  n. i j i j Lemma 5. Let H = (V, E) be a k-uniform hypergraph on n vertices with m > 2 edges and max d(v) = 2. Then the number of vertices whose degree is 1 in hypergraph is n m + l c( H) v2V nm+lc( H) and hypergraph H has, at most, b c pendent edges. k1 Proof. Suppose the number of vertices whose degree is 1 in hypergraph H is t, then hypergraph H has, at most,b c pendent edges. Let the number of vertices whose degree k1 is 2 in hypergraph is x. By c( H) = m(k 1) n + l and å d = km, we have i=1 km = 2x + (n x), x = m l + c( H). So, the number of vertices whose degree is 1 in hypergraph is n m + l c( H) and nm+lc( H) hypergraph H has, at most, b c pendent edges. k1 Axioms 2022, 11, 3 5 of 9 Lemma 6. Let H = (V, E) be a k-uniform hypergraph (k  3) on n vertices with m edges and l = 1 connected components. If k  c( H) + 2, then c( H) = k. Proof. By contradiction, suppose c( H) > k as k  c( H) + 2. If c( H) is k + 1, then there 0 0 0 exists a subhypergraph H of H, which is (k + 1)-critical. Let V = fv , , v g  V( H ) 1 k+1 such that v is colored with color i. Now, we discuss the following two cases. 0 0 0 Case 1. There is a vertex set V in H such that any two vertices in V are in the same edge. 0 0 0 Let H = (V , E ) be a k-uniform hypergraph of n vertices and m edges, with l = 1 0 0 H H 0 0 connected component. Since hypergraph H is k uniform, all vertices of V cannot appear 0 0 in one edge of H . By the condition that any two vertices in vertex set V are in the same edge, there are three vertices in V to form a circle of length 3. Such a cycle is denoted by 0 0 c = v e v e v e v , where e , e , e 2 E 0 and v , v , v 2 V . For any v 2 V nfv , v , v g, 1 1 1 2 2 3 3 1 1 2 3 1 2 3 i 1 2 3 we find that there are two vertices of fv , v , v g such that the two vertices and the vertex 2 3 v can form a cycle of length 3. Assume v and v are such two vertices and the cycle is i 2 3 c = v e v e v e v , where e 2 E 0 is an edge containing v and v , and e 2 E 0 is an i 2 2 3 j i i 2 i i 2 j H H edge containing v and v . If there is not such a cycle c , then the vertices v , v , v and v i 3 i 1 2 3 i must be in the same edge, which is a contradiction with c . So, there must be a cycle c in 1 i hypergraph H for 4  i  k + 1. 0 0 0 00 Let H be the graph obtained from adding the isolated vertices v , , v . Let H be 0 1 k1 the k-uniform hypergraph obtained from H by the following operations of moving edges, S S 0 0 0 0 i.e., e = (e nfv g) fv g and e = (e nfv g) fv g (i = 4, , k + 1). Then, we see 1 1 i i 1 1 i i2 that H is connected and it has no cycles c , c  c . Thus, 1 4 k+1 00 0 0 c( H ) = m (k 1) [n + k 1] + 1, 0 00 0 n + c( H ) = m (k 1) k + 2 and 0 0 n  m (k 1) k + 2. (2) 0 0 0 From c( H ) = m (k 1) n + 1 and Inequality (2), we have 0 0 0 c( H ) = m (k 1) n + 1 0 0 m (k 1) [m (k 1) k + 2] + 1 = k 1  c( H) + 1  c( H ) + 1. 0 0 Then, we obtain that c( H )  c( H ) + 1, which is a contradiction. Case 2. There are at least two vertices in V which are not in the same edge for any 0 0 vertex set V in H . 0 0 0 Let [ H ] be the graph obtained from [ H ] by deleting the vertex whose degree is 0 0 0 0 0 k 1. By Lemma 3, we obtain that c([ H ] ) = c( H ) and [ H ] is (k + 1)-critical. By the 2 2 condition, there are at least two vertices in V which are not in the same edge for any 0 0 0 vertex set V in H , there are at least two vertices in V that are not adjacent. Suppose v is 0 0 0 0 0 not adjacent to v , where v , v 2 V . By Lemma 2, [ H ] is k-edge-connected. Then [ H ] j i j 2 2 contains k pairwise edge-disjoint v v paths. So, H contains k pairwise edge-disjoint j i 0 0 v v paths. Let P , , P be k pairwise edge-disjoint v v paths in H . Let H be the j i 1 k j i 0 0 graph obtained from adding k 1 isolated vertices v , , v . Suppose P contains an 1 k1 edge e and a vertex u such that u 2 e and u 6= v , v , where 1  i  k 1. Let H be the i i i i i i j k-uniform hypergraph obtained from H by the following operations of moving edges, i.e., 0 Axioms 2022, 11, 3 6 of 9 0 0 00 e = (e nfu g) fv g (i = 1, , k 1). Then, we see that H is connected and it has no i i i i paths P , P . Thus, 1 k1 00 0 0 c( H ) = m (k 1) [n + k 1] + 1, 0 00 0 n + c( H ) = m (k 1) k + 2 and 0 0 n  m (k 1) k + 2. (3) 0 0 0 From c( H ) = m (k 1) n + 1 and Inequality (3), we have 0 0 0 c( H ) = m (k 1) n + 1 0 0 m (k 1) [m (k 1) k + 2] + 1 = k 1  c( H) + 1  c( H ) + 1. 0 0 Then we obtain that c( H )  c( H ) + 1, which is a contradiction. For the upper bound about I ( H), due to the lack of effective analysis methods, we only consider k-uniform hypergraph H = (V, E) on n vertices with m > 2 edges, where m nm+1c( H) 2 2 (2 c( H))k + (k 1) c( H) and is an integer. (2 c( H))k + (k 1) c( H) k1 is the maximum number of edges when the diameter of H is less than or equal to 5, where H is a k-uniform hypergraph on n vertices with m edges and the maximum degree 2. Theorem 1. Let H = (V, E) be a k-uniform hypergraph (k  c( H) + 2) on n vertices with nm+1c( H) m > 2 edges, where is an integer and m  (2 c( H))k + (k 1) c( H). Then k1 n n n n h( H)  r(b c + 1) log(b c + 1) + (k r)b c logb c k k k k with the equality holding if and only if p ( H) = p ( H ), where r = nb ck and H is a c c 1 1 k-uniform hypergraph with the maximum degree 2, possessing n vertices and m edges, which has 0 0 nm+1c( H) pendent edges. Then, we see that there is a hypersubgraph H of H with c( H ) = k1 c( H) = c( H ), where the hypergraph H is obtained from jointing two edges by c( H) + 1 common vertices (see Figure 3). Figure 3. The k-uniform c( H)-cyclic hypersubgraph H of H . nm+1c( H) Proof. By Lemma 6, c( H) = k. By Lemma 5, and is an integer, the hypergraph k1 nm+1c( H) H has, at most, pendent edges. For H on n vertices with m > 2 edges and the 1 1 k1 maximum degree 2, there is H that satisfies that the diameter of H is less than or equal to 1 1 5 because of m  (2 c( H))k + (k 1) c( H). By the structure and strong coloring of hypergraph H , the chromatic decomposition sequences obtained from all strong coloring nm+1c( H) of k-uniform hypergraph H are the same and unique when is an integer k1 and d( H )  5 , which is supposed to be p ( H ) = fjV j, ,jV jg. If n is divisible by 1 1 1 k k, then V =  = V in the case of H . Otherwise, V =  = V = b c + 1, j j j j j j j j 1 1 1 r n n n n jV j =  = jV j = b c, where r = nb ck. Thus, h( H ) = r(b c + 1) log(b c + 1) + r+1 k 1 k k k k n n (k r)b c logb c. In addition, jVj V  2 does not hold for any jVj, V 2 p ( H ). c 1 i j i j k k By Lemma 4, there is no such hypergraph H satisfying h( H) < h( H ). This completes the proof. Axioms 2022, 11, 3 7 of 9 From Theorem 1 and Equality (1), we have the following result. Theorem 2. Let H = (V, E) be a k-uniform hypergraph (k  c( H) + 2) on n vertices with nm+1c( H) m > 2 edges, where is an integer and m  (2 c( H))k + (k 1) c( H). Then k1 n n n n r(b c + 1) log(b c + 1) + (k r)b c logb c k k k k I ( H)  log n , the equality holds if and only if p ( H) = p ( H ), where H are given in Theorem 1. c c 1 1 From Theorem 2 and Equality (1), we have the following result. Corollary 1. Let H = (V, E) be a k-uniform (k  3) supertree on n vertices with m > 2 edges, nm+1 2 where is an integer and m  2k + (k 1) . Then k1 n n n n r(b c + 1) log(b c + 1) + (k r)b c logb c k k k k I ( H)  log n with the equality holding if and only if p ( H) = p ( H ), where n = b ck + r (0  r  k 1) c c and H is a k-uniform supertree with the maximum degree 2, possessing n vertices and m edges, nm+1 which has pendent edges. k1 Theorem 3. Let H = (V, E) be a k-uniform hypergraph (k  c( H) + 2) on n vertices with m > 2 edges. Then h( H)  (k 2)m log m + (m c( H)) log(m c( H)) with the equality holding if and only if p ( H) = p ( H ), where the hypergraph H is obtained c c 2 2 from jointing c( H) + 1 edges with two common vertices u and v and jointing m c( H) 1 edges by the vertex v, respectively. (see Figure 4) Figure 4. The k-uniform c( H)-cyclic hypergraph H . Proof. By Lemma 6, c( H) = k. According to the structure and the strong coloring of a hypergraph, the chromatic decomposition sequence obtained from any strong col- oring of H is the same and unique, which is denoted by p ( H ) = fjV j, ,jV jg. 2 c 2 1 k Then jV j =  = jV j = m , jV j = m c( H ) and jV j = 1. So h( H ) = 1 k2 k1 2 k 2 (k 2)m log m + (m c( H )) log(m c( H )). Note that 1  V  m for any strong j j 2 2 i coloring of a hypergraph. For any jVj  V , we see that jVj = 1 or V = m. Sup- i j i j pose there is a hypergraph H = (V, E) with c( H) = c( H ) and its coloring c satisfying 0 0 0 0 h ( H) = h( H). Let p ( H) = V , , V 6= p ( H ). Then there is V  V sat- c c c 1 k i j 0 0 T isfying V < m and V > 1. So, there are e and e satisfying e e 6= Æ. Moreover, 2 2 1 1 j i there is a vertex v 2 e and a vertex v 2 e satisfying v , v 2 V . Suppose u 2 e e , 1 1 2 2 1 2 1 2 i Axioms 2022, 11, 3 8 of 9 then d(u) > 1 and u 2 V . Let e , , e be the other edges of H containing v . Let 3 r 2 H = (V 0 , E 0 ) be a k-uniform hypergraph obtained from H by following operations H H 0 S 0 S of moving edges, i.e., e = (e nfug) fv g and e = (e nfv g) fv g (i = 3, , r). 2 1 i 2 1 Obviously, H is also a k-uniform c( H)-cyclic hypergraph. Then, color the vertex v with the color j noting that its color is i before. Thus, there is a coloring c in H satisfying n o 0 0 0 0 0 p ( H ) = V , , V + 1, , V 1, , V . Then 1 j i k 0 0 0 0 0 h( H) h ( H ) = V log V + V log V 1 j j i i 0 0 0 0 ( V + 1)log( V + 1) ( V 1)log( V 1) j j i i h i 0 0 0 0 = V log V ( V 1)log( V 1) i i i i h i 0 0 0 0 ( V + 1)log( V + 1) V log V j j j j 1 1 = (logx + ) (logx + ) ln2 ln2 < 0, 0 0 0 0 0 0 where x 2 ( V 1, V ) and x 2 ( V , V + 1). That is, h( H) < h ( H )  h( H ), 1 2 i i j j 1 which means that h( H) attains the maximum value as p( H) = p( H ). From Theorem 3 and Equality (1), we have the following result. Theorem 4. Let H = (V, E) be a k-uniform hypergraph (k  c( H) + 2) on n vertices with m > 2 edges. Then (k 2)m log m + (m c( H)) log(m c( H)) log n  I ( H), the equality holds if and only if p ( H) = p ( H ), where H are given in Theorem 3. c c 2 2 From Theorem 4 and Equality (1), we have the following result. Corollary 2. Let H = (V, E) be a k-uniform (k  3) supertree on n vertices with m edges. Then (k 1)m log m log n  I ( H). The equality holds if and only if p ( H) = p (S ). c c m+1 4. Conclusions In this paper, we determine the extremal values for graph entropy based on strong coloring for k-uniform hypergraph H. For k-uniform hypergraph H (k  c( H) + 2) with nm+1c( H) n vertices and m edges, when is an integer and m  (2 c( H))k + (k 1) k1 c( H), we obtain an upper bound of the graph entropy based on strong coloring by using n and k. For k-uniform hypergraph H (k  c( H) + 2) with n vertices and m edges, we obtain a lower bound of graph entropy based on strong coloring by using n, k, m and c( H). Hypergraph is a generalization of a graph. However, there is little research on the entropy of a hypergraph. So, it is meaningful to extend the conclusions of graph entropies based on graphs to hypergraphs in the future. Author Contributions: Conceptualization, methodology, software, software, validation, writing— original draft preparation, L.F.; formal analysis, writing—review and editing, B.D.; supervision, H.Z.; project administration, X.L. All authors have read and agreed to the published version of the manuscript. Axioms 2022, 11, 3 9 of 9 Funding: This research was funded by the Key Laboratory of Tibetan Information Processing Min- istry of Education, Tibetan Information Processing Engineering Technology and Research Center of Qinghai Province, Qinghai-Tibet Plateau Innovation and Talent Introduction Base in Big Data Subject of Language and Culture (Grant No. 111Project D20035), Qinghai Office of Science and Technology (Grant No. 2019-ZJ-7086). Data Availability Statement: Not applicable. Acknowledgments: The authors were very grateful to the referees and the editor for their valuable comments and suggestions, which significantly improved the presentation of this manuscript. Conflicts of Interest: The authors declare no conflict of interest. References 1. Shannon, C.E.; Weaver, W. The Mathematical Theory of Communication; University of Illinois Press: Urbana, IL, USA, 1949. 2. Rashevsky, N. Life, information theory and topology. Bull. Math. Biophys. 1955, 17, 229–235. [CrossRef] 3. Mowshowitz, A. Entropy and the complexity of graphs: I. An index of the relative complexity of a graph. Bull. Math. Biol. 1968, 30, 175–204. [CrossRef] [PubMed] 4. Mowshowitz, A. Entropy and the complexity of graphs: II. The information content of digraphs and infinite graphs. Bull. Math. Biol. 1968, 30, 225–240. [CrossRef] [PubMed] 5. Mowshowitz, A. Entropy and the complexity of graphs: III. Graphs with prescribed information content. Bull. Math. Biol. 1968, 30, 387–414. [CrossRef] 6. Mowshowitz, A. Entropy and the complexity of graphs: IV. Entropy measures and graphical structure. Bull. Math. Biol. 1968, 30, 533–546. [CrossRef] 7. K’orner, J. Coding of an information source having ambiguous alphabet and the entropy of graphs. In Proceedings of the 6th Prague Conference on Information Theory, Prague, Czech Republic, 19–25 September 1973; pp. 411–425. 8. Dehmer, M. Information processing in complex networks: Graph entropy and information functionals. Appl. Math. Comput. 2008, 201, 82–94. [CrossRef] 9. Bonchev, D. Information Theoretic Indices for Characterization of Chemical Structures; Research Studies Press: Chichester, UK, 1983. 10. Dehmer, M.; Mowshowitz, A. A history of graph entropy measures. Inf. Sci. 2011, 181, 57–78. [CrossRef] 11. K’orner, J.; Marton, K. Graphs that split entropies. SIAM J. Discret. Math. 1988, 1, 71–79. [CrossRef] 12. Li, X.; Qin, Z.; Wei, M.; Gutman, I.; Dehmer, M. Novel inequalities for generalized graph entropies–Graph energies and topological indices. Appl. Math. Comput. 2015, 259, 470–479. [CrossRef] 13. Simonyi, G. Perfect graphs and graph entropy, An updated survey. In Perfect Graphs; Ramirez-Alfonsin, J., Reed, B., Eds.; John Wiley & Sons: Hoboken, NJ, USA, 2001; pp. 293–328. 14. Trucco, E. A note on the information content of graphs. Bull. Math. Biol. 1956, 18, 129–135. [CrossRef] 15. Li, X.; Wei, M. Graph entropy: Recent results and perspectives. In Mathematical Foundations and Applications of Graph Entropy; Dehmer, M., Ed.; Wiley-VCH Verlag: Weinheim, Germany, 2016; pp. 133–182. 16. Simonyi, G. Graph entropy: A survey. Comb. Optim. 1995, 20, 399–441. 17. Cao, S.; Dehmer, M.; Shi, Y. Extremality of degree-based graph entropies. Inf. Sci. 2014, 278, 22–33. [CrossRef] 18. Hu, D.; Li, X.L.; Liu, X.G.; Zhang, S.G. Extremality of Graph Entropy Based on Degrees of Uniform Hypergraphs with Few Edges. Acta Math. Sin. 2019, 35, 1238–1250. [CrossRef] 19. Fan, Y.-Z.; Liu, A.-H.; Peng, X.-X.; Tan, Y.-Y. Maximizing spectral radii of uniform hypergraphs with few edges. Discuss. Math. Graph Theory 2016, 36, 845. [CrossRef] 20. Bretto, A. Hypergraph Theory; Springer: Berlin/Heidelberg, Germany, 2013. 21. Berge, C. Hypergraphs; North-Holland: Amsterdam, The Netherlands, 1989. 22. Gionfriddo, M.; Milazzo, L.; Voloshin, V. Hypergraphs and Designs; Nova Publishers: New York, NY, USA, 2015. 23. Hu, S.; Qi, L.; Shao, J.-Y. Cored hypergraphs, power hypergraphs and their Laplacian H-eigenvalues. Linear Algebra Its Appl. 2013, 439, 2980–2998. [CrossRef] 24. Chartrand, G.; Lesniak, L.; Zhang, P. Graphs and Digraphs; Brooks/Cole Pub. Co.: Pacific Grove, CA, USA, 2011. 25. Li, H.; Shao, J.-Y.; Qi, L. The extremal spectral radii of k -uniform supertrees. J. Comb. Optim. 2015, 32, 741–764. [CrossRef]

Journal

Axioms – Multidisciplinary Digital Publishing Institute

Published: Dec 22, 2021

Keywords: hypergraph; graph entropy; strong coloring

There are no references for this article.