2 Main results
Lemma 2.1
For 
, we have
Proof
The graph has vertices and edges. It suffices to consider the maximum and minimum value of such that the number of 0-and 1-vertices are both .
Suppose is even. We consider two cases.
Case (a). is maximum. Assume that of the vertices are labeled with 0 and the remaining vertices are labeled with 1. We consider four subcases.
Subcase (1). or . In this case, , . So, .
Subcase (2). . In this case, without loss of generality, is attained if for , and all other vertices are labeled with 1. Hence, , and .
Subcase (3). . In this case, without loss of generality, is attained if for , and , and all other vertices are labeled with 1. Hence, , and . Therefore, maximal of or when or , respectively. Hence, when , and when .
Subcase (4). . In this case, without loss of generality, is attained if when , , and all other vertices are labeled with 1. Hence, and . Therefore, maximal of or when or , respectively. Hence, for , and when .
Case (b). is maximum. Assume that of the vertices are labeled with 0 and the remaining vertices of are labeled with 1. We consider two subcases.
Subcase (1). or . In this case, , . So, .
Subcase (2). . In this case, without loss of generality, is attained if for , , and all other vertices are labeled with 1. Hence, with maximal is attained when . Therefore, maximal of .
Suppose is odd. We also consider two cases.
Case (a). is maximum. Assume that of the vertices are labeled with 0 and the remaining vertices are labeled with 1. We consider three subcases.
Subcase (1). or . In this case, , . So, .
Subcase (2). . In this case, without loss of generality, is attained if for , and , and all other vertices labeled with 1. Hence, , and . Therefore, maximal of or when or , respectively. Hence, when , and when .
Subcase (3). . In this case, without loss of generality, is attained if when and , and all other vertices are labeled with 1. Hence, and . Therefore, maximal of or when or , respectively. Hence, for , and when .
Case (b). is maximum. Assume that of the vertices are labeled with 0 and the remaining vertices are labeled with 1. We consider two subcases.
Subcase (1). or . In this case, , . So, .
Subcase (2). . In this case, without loss of generality, is attained if for , and all other vertices labeled with 1. Hence, . Therefore, maximal of for both or . We note that for , we have .
Combining the above arguments, the lemma holds. ■
Lemma 2.2
For , the second largest value in
Proof
From the proof of Lemma 2.1, we know that is attained when all the vertices of are of same label. Otherwise, we have , or for odd whereas for even .
When is odd, for . Hence, for , the second largest value of is , and the second largest value of is for . Observe that when , Case (a) of the proof of Lemma 2.1 gives the second largest value , whereas Case (b) gives the same largest values of in both subcases when or . Hence, the second largest value is given by or which implies that .
When is even, by a similar argument, we have for the second largest value of is ; and for , the second largest value of is .
By the labeling methods described in the proof of Lemma 2.1, we know all the above second largest values are attainable. The proof is thus complete. ■
The following lemma is easy to obtain.
Lemma 2.3
If we label of the vertices of by and the remaining vertices by , then , , .
Lemma 2.4
For , let . Suppose we label of the vertices with even subscript and of the vertices with odd subscript by , and label the remaining vertices by , then
(1) if ;
(2) if for even , or for odd ;
(3) if for even , or for odd .
Proof
Denote by the friendly labeling graph of a with . Since the labeling we consider is friendly, by Lemma 1.2, we know is always even.
(1) Obvious.
(2) For even with , let be labeled by , and the remaining vertices be labeled by . We now get . If , then we are done. We now assume . If we now exchange the labels of and in , we get . Beginning , we then exchange the labels of and for successively. We can get successively. Repeating the same procedure to the labels of and in for , we then get . For odd with , we repeat the above procedure except that in getting , we exchange the labels of and for only. Hence, .
(3) For even with , we note that is attained if are labeled by and the remaining vertices labeled by . We now get . If we now exchange the labels of and , we then get . If , we are done. We now assume . Beginning , we exchange the labels of and for successively. We then get successively. Repeating the same procedure to the labels of and in for , we then get . For odd with , we repeat the above procedure except that in getting , we exchange the labels of and for . Hence, . The proof is thus complete. ■
Theorem 2.5
For , we have for .
Proof
By the definition of friendly indices, we only need to show that all the expressions in the theorem are the indices of all the possible friendly labelings of .
Let be even. Label () of the vertices () by and the remaining vertices by , then for the vertices (), there exist vertices labeled by and the remaining vertices by . By Lemmas 2.3 and 2.4 we know the number of 0-edges in is . Consider induced by the edges . If , the number of 0-edges in is so that . If , we have . Therefore, we have obtained all the possible labeling graphs of . Consequently, . Hence, .
Similarly, when is odd, we label () of the vertices () by and the remaining vertices by , then for the vertices (), there exist vertices labeled with and the remaining vertices by . We can obtain a similar conclusion as above. This completes the proof. ■
Example 2.1
For , we have: ; ; ; ; ; ; ; ; and .
Let . Observe that if is odd, then for . If is even, then for . For , we can check that an expression in Theorem 2.5 is 0 when and are of same parity. For or , we can check that . Hence, we have
Corollary 2.6
The graph is not cordial if and only if is even.
By Lemma 2.2 and Example 2.1, we also have
Corollary 2.7
forms an arithmetic sequence if and only if .
