Entropy of symmetric graphs

Entropy of symmetric graphs

Discrete Mathematics 339 (2016) 475–483 Contents lists available at ScienceDirect Discrete Mathematics journal homepage: www.elsevier.com/locate/dis...

410KB Sizes 0 Downloads 52 Views

Discrete Mathematics 339 (2016) 475–483

Contents lists available at ScienceDirect

Discrete Mathematics journal homepage: www.elsevier.com/locate/disc

Entropy of symmetric graphs Seyed Saeed Changiz Rezaei ∗ , Chris Godsil Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada

article

abstract

info

Article history: Received 29 July 2014 Received in revised form 7 March 2015 Accepted 28 September 2015 Available online 18 October 2015 Keywords: Graph entropy Fractional chromatic number Vertex packing polytope Perfect graphs

Let FG (P ) be a functional defined on the set of all the probability distributions on the vertex set of a graph G. We say that G is symmetric with respect to FG (P ) if the distribution P ∗ maximizing FG (P ) is uniform on V (G). Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we prove that vertex-transitive graphs are symmetric with respect to graph entropy. As the main result of this paper, we prove that a perfect graph is symmetric with respect to graph entropy if and only if its vertices can be covered by disjoint copies of its maximum-size clique. Particularly, this means that a bipartite graph is symmetric with respect to graph entropy if and only if it has a perfect matching. © 2015 Elsevier B.V. All rights reserved.

1. Introduction The entropy of a graph is an information theoretic functional which is defined on a graph with a probability distribution on its vertex set. This functional was originally proposed by J. Körner in 1973 to study the minimum number of codewords required for representing an information source (see J. Körner [8]). Let V P (G) be the vertex packing polytope of a given graph G which is the convex hull of the characteristic vectors of its independent sets. Let |V (G)| = n and P be a probability distribution on V (G). Then the entropy of G with respect to the probability distribution P is defined as H (G, P ) = min

a∈V P (G)

n 

pi log(1/ai ).

i=1

G. Simonyi [18] showed that the maximum of the graph entropy of a given graph over the probability distribution of its vertex set is equal to the logarithm of its fractional chromatic number. We say a graph is symmetric with respect to graph entropy if the uniform distribution maximizes its entropy. It is worth noting that the notion of a symmetric graph with respect to a functional was already defined by G. Greco in [7]. In this paper, we study some classes of graphs which are symmetric with respect to graph entropy. For example we show that vertex-transitive graphs are symmetric; however, our main results are the following theorems and corollary. Theorem. Let G = (V , E ) be a perfect graph and P be a probability distribution on V (G). Then G is symmetric with respect to graph entropy H (G, P ) if and only if G can be covered by disjoint copies of its maximum-size cliques. As a corollary to above theorem, we have



Corresponding author. E-mail addresses: [email protected] (S.S. Changiz Rezaei), [email protected] (C. Godsil).

http://dx.doi.org/10.1016/j.disc.2015.09.020 0012-365X/© 2015 Elsevier B.V. All rights reserved.

476

S.S. Changiz Rezaei, C. Godsil / Discrete Mathematics 339 (2016) 475–483

(a) A 5-cycle G.

(b) A triangle F .

(c) The graph Gu1 ←−F .

Fig. 1.

Corollary. Let G be a bipartite graph with parts A and B, and no isolated vertices. Then, uniform probability distribution U over the vertices of G maximizes H (G, P ) if and only if G has a perfect matching. A. Schrijver [17] calls a graph G a k-graph if it is k-regular and its fractional-edge chromatic number χf′ (G) is equal to k. We show that. Theorem. Let G be a k-graph with k ≥ 3. Then the line graph of G is symmetric with respect to graph entropy. As a corollary to this result we show that the line graph of every bridgeless cubic graph is symmetric with respect to graph entropy. J. Körner investigated the basic properties of the graph entropy in several papers from 1973 till 1992 (see J. Körner [8–10, 13,11,12]). Let F and G be two graphs on the same vertex set V . Then the union of graphs F and G is the graph F ∪ G with vertex set V and its edge set is the union of the edge set of graph F and the edge set of graph G. That is V (F ∪ G) = V , E (F ∪ G) = E (F ) ∪ E (G) . The most important property of the entropy of a graph is that it is sub-additive with respect to the union of graphs, that is H (F ∪ G, P ) ≤ H (F , P ) + H (G, P ) . This leads to the application of graph entropy for graph covering problems. The graph covering problem can be described as follows. Given a graph G and a family of graphs G where each graph Gi ∈ G has the same vertex set as G, we want to cover the edge set of G with the minimum number of graphs from G. Using the sub-additivity of graph entropy one can obtain lower bounds on this number. Graph entropy was implicitly used to give a non-trivial estimation in an unsolved combinatorial problem (see Fredman and Komlós [4]). It is worth mentioning that the notion of graph entropy was explicitly defined in J. Körner [9]. 2. Preliminaries 2.1. Entropy of graphs Let G be a graph on vertex set V (G) = {1, . . . , n}, and P = (p1 , . . . , pn ) be a probability distribution on V (G).

n

1 Remark 2.1. Note that the function i=1 pi log ai in the definition of the graph entropy is a convex function. It tends to infinity at the boundary of the non-negative orthant and tends monotonically to −∞ along the rays from the origin. 

The main properties of graph entropy are monotonicity, sub-additivity, and additivity under vertex substitution. Monotonicity is formulated in the following lemma (see G. Simonyi [18]). Lemma 2.1 (J. Körner). Let F be a spanning subgraph of a graph G. Then for any probability distribution P we have H (F , P ) ≤ H (G, P ). We already explained the sub-additivity in the introduction section. It is worth noting that the sub-additivity was first recognized by Körner in [9]. The notion of substitution is defined as follows. Let F and G be two vertex disjoint graphs and v be a vertex of G. We substitute F for v by deleting v and joining all vertices of F to those vertices of G which have been adjacent with v . Let Gv←F be the resulting graph. The substitution operation is illustrated in Fig. 1.

S.S. Changiz Rezaei, C. Godsil / Discrete Mathematics 339 (2016) 475–483

477

We extend the notion of substitution to distributions. Let P and Q be the probability distributions on V (G) and V (F ), respectively. Then the probability distribution Pv←Q on V (Gv←F ) is given by Pv←Q (x) = P (x) if x ∈ V (G)\{v} and Pv←Q (x) = P (x)Q (x) if x ∈ V (F ). Now we state the following lemma which was proved in J. Körner et al. [13]. Lemma 2.2 (J. Körner, G. Simonyi, and Zs. Tuza). Let F and G be two vertex disjoint graphs, v a vertex of G, while P and Q are probability distributions on V (G) and V (F ), respectively. Then we have H Gv←F , Pv←Q = H (G, P ) + P (v)H (F , Q ) . 





Notice that the entropy of an empty graph (a graph with no edges) is always zero (regardless of the distribution on its vertices). Noting this fact, we have the following corollary as a consequence of Lemma 2.2. Corollary 2.3. Let Gi be the ith connected component of graph G and P be a probability distribution on V (G). If x ∈ V (Gi ), set Pi (x) = P (x) (P (V (Gi )))−1 ,

x ∈ V (Gi ).

Then H (G, P ) =



P (V (Gi )) H (Gi , Pi ) .

i

The following lemmas give the entropy of some special graphs (see G. Simonyi [19] and [18]). Lemma 2.4. For Kn , the complete graph on n vertices, one has H (Kn , P ) = H (P ).



The next one is the complete multipartite graph. Let G = Km1 ,m2 ,...,mk denote a complete k-partite graph with parts of size m1 , m2 , . . . , mk . Then we have the following lemma. Lemma 2.5. Let G = Km1 ,m2 ,...,mk . Given  a distribution P on V (G) let Q be the distribution on S (G), the set of maximal independent sets of G, given by Q (J ) =  x∈J P (x) for each J ∈ S (G). Then H (G, P ) = H (Kk , Q ). A special case of the above lemma is the entropy of a complete bipartite graph with equal probability distributions on its parts. Now, let G be a bipartite graph with parts A and B. For a subset D ⊆ A, let N (D) denote the set of neighbours of D in B, that is a subset of the vertices in B which are adjacent to a vertex in A. Given a distribution P on V (G) we have P (D) =



pi ,

∀D ⊆ V (G).

i∈D

Furthermore, defining the binary entropy as h(x) := −x log x − (1 − x) log(1 − x),

0 ≤ x ≤ 1.

The following theorem was proved by J. Körner and K. Marton (see [11] and Theorem 3.8 of [19]). Theorem 2.6 (J. Körner and K. Marton). Let G be a bipartite graph with no isolated vertices and P be a probability distribution on its vertex set. If P (D) P (A)



P (N (D)) P (B)

,

for all subsets D of A, then H (G, P ) = h (P (A)) . If P (D) P (A)

>

P (N (D)) P (B)

for some subset D of A,

then there exist a partition of A = D1 ∪ · · · ∪ Dk and a partition of B = U1 ∪ · · · ∪ Uk such that H (G, P ) =

k  i=1

P (Di ∪ Ui ) h



P (Di ) P (Di ∪ Ui )



. 

478

S.S. Changiz Rezaei, C. Godsil / Discrete Mathematics 339 (2016) 475–483

3. Graph entropy, fractional chromatic number, and symmetric graphs The relation between the entropy of a graph and its fractional chromatic number was established by G. Simonyi [18]. We recall that the fractional chromatic number of a graph G denoted by χf (G) is the minimum sum of nonnegative weights on the independent sets of G such that for any vertex the sum of the weights on the independent sets of G containing that vertex is at least one (see C. Godsil and G. Royle [6] sections 7.1 to 7.5). The following lemma was proved in G. Simonyi [18]. Lemma 3.1 (G. Simonyi). For a graph G and probability distribution P on its vertices with fractional chromatic number χf (G), we have max H (G, P ) = log χf (G). P

We call a graph symmetric with respect to graph entropy if its entropy is maximized with uniform probability distribution over its vertex set. In this section, we characterize different classes of graphs which are symmetric with respect to graph entropy. Particularly, we consider symmetric bipartite graphs, symmetric perfect graphs, and symmetric line graphs. First we show that every vertex-transitive graph is symmetric with respect to graph entropy. Theorem 3.2. Let G be a vertex-transitive graph. Then the uniform distribution U over the vertices of G maximizes H (G, P ). That is H (G, U ) = log χf (G). Proof. Setting n = |V (G)|, we have H (G, U ) =

1 

min

a∈V P (G)

n v∈V (G)

n

≥ log  v

av

,

≥ min log a∈V P (G)

= log χf (G),

log

1 av

= min log a∈V P (G)



1

 1n

av

Geometric–Harmonic mean inequality n

α(G)

,

since

 v

av ≤ α(G) for every a ∈ V P (G)

since G is a vertex-transitive graph.

Then the above inequalities along with Lemma 3.1 complete the proof.



The following example shows that the converse of the above theorem is not true. Consider a bipartite graph G = C4 ∪ C6 , with vertex sets V (C4 ) = {v1 , v2 , v3 , v4 } and V (C6 ) = {v5 , v6 , v7 , v8 , v9 , v10 }, and parts A = {v1 , v3 , v5 , v7 , v9 }, B = {v2 , v4 , v6 , v8 , v10}. Clearly, G is not a vertex-transitive graph, however, using Theorem 2.6, one can see that the uniform 1 1 distribution U = 10 , . . . , 10 gives the maximum graph entropy which is 1. Remark 3.1. Note that the probability distribution which maximizes the graph entropy is not unique. Consider C4 with vertex set V (C4 ) = {v1 , v2 , v3 , v4 } with parts A = {v1 , v3 } and B = {v2 , v4 }. Using Theorem 2.6, probability distributions P1 = ( 41 , 14 , 14 , 14 ) and P2 = ( 18 , 14 , 38 , 41 ) give the maximum graph entropy which is 1. 3.1. Symmetric perfect graphs Let G = (V , E ) be a graph. Recall that the fractional vertex packing polytope of G, i.e., FV P (G) is defined as

 FVP (G) :=

x∈

 |V | R+

:



xv ≤ 1 for all cliques K of G .

v∈K

Note that for every graph G, we have V P (G) ⊆ FVP (G). The following theorem was proved in V. Chvátal [3] and D.R. Fulkerson [5]. Theorem 3.3. A graph G is perfect if and only if V P (G) = FVP (G).



The following theorem which is called weak perfect graph theorem is useful in the following discussion. The weak perfect graph theorem was proved by Lovász in [14]. It is worth mentioning that a generalization of this theorem is proved [15]. Theorem 3.4. A graph G is perfect if and only if its complement is perfect.



S.S. Changiz Rezaei, C. Godsil / Discrete Mathematics 339 (2016) 475–483

479

Now, we prove the following theorem which characterizes perfect graphs which are symmetric with respect to graph entropy. Theorem 3.5. Let G = (V , E ) be a perfect graph and P be a probability distribution on V (G). Then G is symmetric with respect to graph entropy H (G, P ) if and only if G can be covered by disjoint copies of its maximum-size cliques.

˙ ···∪ ˙ V (Qm ) and Proof. Suppose G is covered by its maximum-sized cliques, say Q1 , . . . , Qm . That is V (G) = V (Q1 )∪ |V (Qi )| = ω(G), ∀i ∈ [m]. m Now, consider graph T which is the disjoint union of the subgraphs induced by V (Qi ) ∀i ∈ [m]. That is T = ˙ i=1 G [V (Qi )]. Using Lemma 3.1, we have



H (T , P ) ≤ log χf (T ),

∀P .

Noting that χf (T ) ≤ χf (G), since T is a subgraph of G, and the above inequality we get H (T , P ) ≤ log χf (G),

∀P .

(1)

Then noting that G is a perfect graph, the fact that complete graphs are symmetric with respect to graph entropy, χf (Qi ) = χf (G) = ω(G) = χ (G), ∀i ∈ [m], (1), and Corollary 2.3, we conclude that uniform distribution maximizes H (G, P ). Now, suppose that G is symmetric with respect to graph entropy. We prove that G can be covered by its maximum-sized cliques. Suppose this is not true. We show that G is not symmetric with respect to H (G, P ). Letting G be the complement of graph G and denoting the independence number of G by α(G), from perfection of G and weak perfect theorem, we get χ (G) = α(G), i.e., clique cover number of G is equal to the independence number of G. Then, |V (G)| using this fact, our assumption implies that G has an independent set S with |S | = α > ω(G) . 1−

|S |

We define a vector x such that xv = |V | if v ∈ S and xv = ω−|V1| if v ∈ V (G)\ S. Then, we can see that x ∈ FVP (G) = V P (G). |S | Let t := |V | . Then, noting that t > ω1 , |S |

H (G, U ) ≤ −

=−

1 

|V | 1

|V |

log xv

v∈V



 

log xv +

v∈S



xv

v∈V \S

  1−t |S | log t + (|V | − |S |) log |V | ω−1 1−t = −t log t − (1 − t ) log ω−1   1−t 1−t = −t log t − (ω − 1) log < log ω(G).  ω−1 ω−1 =−

1

The above theorem about symmetric perfect graphs is specialized to bipartite graphs in the following corollary. We give a separate proof for the following corollary, in S.S.C. Rezaei [2], using Hall’s theorem, König’s theorem (see D. West [20] section 3.1) and Theorem 2.6. Corollary 3.6 (Symmetric Bipartite Graphs). Let G be a bipartite graph with parts A and B, and no isolated vertices. Then, uniform probability distribution U over the vertices of G maximizes H (G, P ) if and only if G has a perfect matching. We also have the following corollary. Corollary 3.7. Let G be a connected regular line graph with valency k at least 4. Then if G is covered by copies of its disjoint maximum-size cliques, then G is symmetric with respect to H (G, P ). Proof. Let G = L(F ) for some graph F . Then we claim that either F is bipartite or regular. Consider two adjacent u, w ∈ V (F ). Indeed, since G is k-regular, for every pair of adjacent vertices u, w ∈ V (F ) we have deg (u) + deg (w) − 2 = k.

(2)

If deg (u) = deg (w), then the above equality and the connectedness of G imply that deg (v) = 2k + 1, ∀v ∈ V (F ). Therefore, the underlying graph F is regular. On the other hand, if deg (u) ̸= deg (w), then using (2) and the connectedness of G, for every vertex v of G either we have deg (v) = deg (u) or deg (v) = deg (w). Furthermore, since G is k-regular, each edge of F connects a vertex of degree deg (u) to a vertex of deg (w) and vertices of degree deg (u) and deg (w) form two independent sets, respectively. Thus F is bipartite.

480

S.S. Changiz Rezaei, C. Godsil / Discrete Mathematics 339 (2016) 475–483

If F is bipartite, then G is perfect and because of Theorem 3.5 we are done. So suppose that F is not bipartite. Then each clique of size k in G corresponds to a vertex v in V (F ) and the edges incident to v in F and vice versa. That is because any such cliques in G contains a triangle and there is only one way extending that triangle to the whole clique which corresponds to edges incident with the corresponding vertex in F . This implies that the covering cliques in G give an independent set in F which is also a vertex cover in F . Hence F is a bipartite graph and hence G is perfect. Then due to Theorem 3.5 the theorem is proved.  Now, considering that finding the clique number of a perfect graph can be computed in polynomial time and using the weak perfect graph theorem, we conclude that one can decide in polynomial time whether a perfect graph is symmetric with respect to graph entropy. 3.2. Symmetric line graphs Let G be a line graph of some graph F , i.e., G = L(F ). Let |V (F )| = n and |E (F )| = m. Note that every matching in F corresponds to an independent set in G and every independent set in G corresponds to a matching in F . Furthermore, the fractional edge-chromatic number of F , i.e., χf′ (F ) is equal to the fractional chromatic number of G, i.e., χf (G). Thus

χf′ (F ) = χf (G). Moreover, note that the vertex packing polytope V P (G) of G is the matching polytope MP (F ) of F (see L. Lovász and M.D. Plummer [16] chapter 12). That is V P (G) = MP (F ). These facts motivate us to study line graphs which are symmetric with respect to graph entropy. For a set W ⊆ V , we use

δ(W ) := {{w, v} ∈ E (F ) : w ∈ W , v ∈ V \W }. Furthermore, we define



x(δ(v)) :=

xe ,

e∈δ(v)



x (E [W ]) :=

xe .

e∈E (F [W ])

We recall that a vector x ∈ Rm + is in the matching polytope MP (F ) of the graph F if and only if it satisfies (see A. Schrijver [17])

∀e ∈ E (F ), ∀v ∈ V (F ),

xe ≥ 0 x(δ(v)) ≤ 1 x (E [W ]) ≤



(3)

 |W | , ∀W ⊆ V (F ) with |W | odd.

1 2

Let M denote the family of all matchings in F , and for every matching M ∈ M let the characteristic vector bM ∈ Rm + be as

(bM )e =

1, 0,

e ∈ M, e ̸∈ M .



(4)

Then the fractional edge-chromatic number χf′ (F ) of F is defined as



 

χf (F ) := min ′

λM |λ ∈ R+ ,

M ∈M

M



λM (bM )e = 1, ∀e ∈ E (F ) .

e∈M ∈M

If we restrict λM to be an integer, then the above definition gives rise to the edge-chromatic number of F , i.e., χ ′ (F ). Thus

χf′ (F ) ≤ χ ′ (F ). As an example considering F to be the Petersen graph, we have

χf′ (F ) = 3 < χ ′ (F ) = 4. The following theorem which was proved by Edmonds, gives a characterization of the fractional edge-chromatic number

χf′ (F ) of a graph F (see A. Schrijver [17] section 28.6).

Theorem 3.8. Let ∆(F ) denote the maximum degree of F . Then the fractional edge-chromatic number of F is obtained as

 |E (F [W ])| χf (F ) = max ∆(F ), max .  W ⊆V , |W |≥3 ⌊ 1 |W |⌋ 2 



S.S. Changiz Rezaei, C. Godsil / Discrete Mathematics 339 (2016) 475–483

481

Following A. Schrijver [17] we call a graph F a k-graph if it is k-regular and its fractional edge-chromatic number χf′ (F ) is equal to k. The following corollary characterizes a k-graph (see A. Schrijver [17] section 28.6). Corollary 3.9. Let F be a k-regular graph. Then χf′ (F ) = k if and only if |δ(W )| ≥ k for each odd-element subset W of V (F ). The following theorem introduces a class of symmetric line graphs with respect to graph entropy. The main tool in the proof of the following theorem is Karush–Kuhn–Tucker (KKT) optimality condition in convex optimization (see S. Boyd, and L. Vanderberghe [1] section 5.5.3). Theorem 3.10. Let F be a k-graph with k ≥ 3. Then the line graph G = L(F ) is symmetric with respect to graph entropy. Proof. From our discussion above we have



H (G, P ) = min

x∈MP (F )

pe log

e∈E (F )

1 xe

.

Let λv , γW ≥ 0 be the Lagrange multipliers corresponding to inequalities x(δ(v)) ≤ 1 and x (E [W ]) ≤ ⌊ 12 |W |⌋ in the description of the matching polytope MP (F ) in (3) for all v ∈ V (F ) and for all W ⊆ V (F ) with |W | odd, and |W | ≥ 3, respectively. From our discussion in Remark 2.1, the Lagrange multipliers corresponding to inequalities xe ≥ 0 are all zero. Set g (x) = −



pe log xe .

e∈E (F )

Then the Lagrangian of g (x) is L (x, λ, γ) = −





pe log xe +





e∈E (F )

W ⊆V , W ∋e,|W | odd, |W |≥3

+

(λu + λv ) (xe − 1)

e={u,v}

e∈E (F )

γ W xe −

 W ⊆V , |W | odd, |W |≥3



1 2

 |W | .

(5)

Using KKT conditions (see S. Boyd, and L. Vanderberghe [1] section 5.5.3), the vector x∗ minimizes g (x) if and only if it satisfies

∂L = 0, ∂ x∗e →−

pe x∗

+ (λu + λv ) +



γW = 0 for e = {u, v}.

(6)

W ⊆V , W ∋e,|W | odd, |W |≥3

e

Fix the probability distribution to be uniform over the edges of F , that is pe =

1 m

,

∀e ∈ E (F ).

Note that the vector variables as x∗ =

1

1 k

is a feasible point in the matching polytope MP (F ). Now, one can verify that specializing the

,

k γW = 0 ∀ W ⊆ V , |W | odd, |W | ≥ 3 k λu = λv = ∀ e = {u, v} 2m satisfies Eqs. (6). Thus H (G, U ) = log k. Then using Lemma 3.1 and the assumption χf (G) = k the theorem is proved.



Let G = (V , E ) be a graph and let W be a subset of its vertex set V . Then δ(W ) denotes the set of edges of G with exactly one end in W . Now we have the following interesting statement for every cubic bridgeless graph. Corollary 3.11. The line graph of every cubic connected bridgeless graph F is symmetric with respect to graph entropy.

482

S.S. Changiz Rezaei, C. Godsil / Discrete Mathematics 339 (2016) 475–483

Fig. 2. A bridgeless cubic graph.

Fig. 3. A cubic one-edge connected graph.

Proof. Let W ⊆ V (F ) and let Z ⊆ W consist of vertices v such that δ(v) ∩ δ(W ) = ∅. Then using the fact that the sum of degrees is twice the number of edges for F [W ], we have 3|Z | + 3|W \Z | − |δ(W )| = 2|E (F [W ])|. Consequently, 3|W | ≡ |δ(W )| mod 2. Assuming |W | is odd and noting that F is bridgeless, we have

|δ(W )| ≥ 3. Then, considering Corollary 3.9, the corollary is proved.



Fig. 2 shows a bridgeless cubic graph which is not edge transitive and its edges are not covered by disjoint copies of stars and triangles. Thus the line graph of the shown graph in Fig. 2 is neither vertex-transitive nor covered by disjoint copies of its maximum size cliques. However, it is symmetric with respect to graph entropy by Corollary 3.11. Fig. 3 shows a cubic graph with a bridge. The fractional edge-chromatic number of this graph is 3.5 while the entropy of its line graph is 1.75712, i.e., log2 3.5 = 1.8074 > 1.75712. Thus, its line graph is not symmetric with respect to graph entropy, and we conclude that Corollary 3.11 is not true for cubic graphs with bridges in general. 4. Open questions In this section we point out some of the problems that are worth considering for future research. 4.1. Symmetric graphs We defined symmetric graphs with respect to graph entropy in this paper. As the main result of this paper, we characterized symmetric perfect graphs. Furthermore, we proved that there are some other classes of graphs such as vertextransitive graphs and line graph of bridgeless cubic graphs which are symmetric with respect to graph entropy. From what discussed above and the symmetric graphs considered in this paper, the next natural class of graphs to consider is strongly regular graphs. It is worth investigating if strongly regular graphs are symmetric with respect to graph entropy. For the study of the structural properties of strongly regular graphs see Godsil and Royle [6] chapter 10. Furthermore, it is worth noting that finding the main properties of symmetric graphs with respect to graph entropy is another interesting open problem.

S.S. Changiz Rezaei, C. Godsil / Discrete Mathematics 339 (2016) 475–483

483

References [1] Stephen Boyd, Lieven Vanderberghe, Convex Optimization, Cambridge University Press, New York, 2004, First published in 2004, Seventh printing with corrections in 2009. [2] Seyed Saeed Changiz Rezaei, Entropy and Graphs (Master of Math thesis), Combinatorics and Optimization Department of the University of Waterloo, 2013. [3] V. Chvátal, On certain polytopes associated with graphs, J. Comb. Theory B 18 (1975) 138–154. [4] M. Fredman, J. Komlós, On the size of separating systems and perfect hash functions, SIAM J. Algebr. Discrete Methods 5 (1984) 61–68. [5] D.R. Fulkerson, Blocking and anti-blocking of polyhedra, Math. Program. 1 (1971) 168–194. [6] Chris Godsil, Gordon Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001. [7] G. Greco, Capacities of graphs and 2-matchings, Discrete Math. 186 (1–3) (1998) 135–143. [8] J. Körner, Coding of an information source having ambiguous alphabet and the entropy of graphs, in: Transactions of the 6th Prague Conference on Information Theory, Academia, Prague, 1973, pp. 411–425. [9] J. Körner, Fredman-Komlós bounds and information theory, SIAM J. Algebr. Discrete Methods 7 (1986) 560–570. [10] J. Körner, G. Longo, Two-step encoding of finite memoryless sources, IEEE Trans. Inf. Theory 19 (1973) 778–782. [11] J. Körner, K. Marton, Graphs that split entropies, SIAM J. Discrete Math. 1 (1988) 71–79. [12] J. Körner, K. Marton, New bounds for perfect hashing via information theory, European J. Combin. 9 (1988) 523–530. [13] J. Körner, G. Simonyi, Zs. Tuza, Perfect couples of graphs, Combinatorica 12 (1992) 179–192. [14] L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (3) (1972) 253–267. [15] L. Lovász, A characterization of perfect graphs, J. Combin. Theory Ser. B 13 (2) (1972) 95–98. [16] L. Lovász, M.D. Plummer, Matching Theory, North-Holland Publishing Co., Amsterdam, 1986. [17] Alexander Schrijver, Combinatorial Optimization, Springer-Verlag, Berlin, 2003. [18] G. Simonyi, Perfect graphs and graph entropy. An updated survey, in: Perfect Graphs, John Wiley and Sons, 2001, pp. 293–328. [19] G. Simonyi, Graph entropy: a survey, in: Combinatorial Optimization, W. Cook, L. Lovas, P. Seymour, (Eds.) DIMACS Series in Discrete Mathematics and Computer Science, vol. 20, AMS, pp. 399–441. [20] Douglas B. West, Introduction to Graph Theory, second ed., Prentice-Hall, Inc., 2001.