On Point-Color-Symmetric Graphs and Groups with Point-Color-Symmetric Picture Representation

• Main Author: Fernandez, Patrick John
• Format: text
• Published: Archīum Ateneo 2020
• Subjects: Point-color-symmetric graph, picture, graph representation
• Online Access: https://archium.ateneo.edu/theses-dissertations/428
• Institution: Ateneo De Manila University

In 1979, Chen and Teh introduced the concept of point-color-symmetric (PCS) graphs and determined a necessary and sufficient condition for a graph to be PCS. Extending this, Marcelo et al. in 1994 defined conditions for a PCS graph to be a PCS picture representation (PPR) for a group and also determined a necessary and sufficient condition for a group to have a PPR. However, the determination of all groups with a PPR is not yet complete. This work determines necessary and sufficient conditions for the circulant graph C(n : i) to have a PCS edge coloring and a sufficient condition for C(n : i, j) to have a PCS edge coloring. A necessary and sufficient condition for the complete bipartite graph Km,n to have a PCS edge coloring is also shown. In addition, it is shown that for n > 1, the n-dimensional hypercube graph Qn has a PCS edge coloring with n colors, and that no wheel graph has a PCS edge coloring. Moreover, we show that for n > 2, the dihedral group Dn of order 2n has a PPR with two colors and a PPR with n colors and that the underlying graphs of these PPRs are C2n and Kn,n. Extending this to a larger group, a characterization for groups of the form Dn × Z2 to have a PPR is also determined. Boolean groups, that is, groups of the form Z n 2 are also shown to have a PPR that is precisely Qn. Finally, using the computational software GAP, we determine some finite Coxeter groups that have a PPR.