Distinguishing colorings of Cartesian products of complete graphs

被引：29
作者：
Fisher, Michael J. [1 ]
Isaak, Garth [2 ]
机构：
[1] Calif State Univ Fresno, Dept Math, Fresno, CA 93740 USA
[2] Lehigh Univ, Dept Math, Bethlehem, PA 18015 USA
来源：
DISCRETE MATHEMATICS | 2008年 / 308卷 / 11期
关键词：
edge coloring; automorphism; distinguishing number;
D O I：
10.1016/j.disc.2007.04.070
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We determine the values of s and t for which there is a coloring of the edges of the complete bipartite graph K-s,K-t which admits only the identity automorphism. In particular, this allows us to determine the distinguishing number of the Cartesian product of complete graphs. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：2240 / 2246
页数：7
相关论文
共 50 条
  • [21] Extending partial edge colorings of iterated cartesian products of cycles and paths
    Casselgren, Carl Johan
    Granholm, Jonas B.
    Petros, Fikre B.
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2024, 26 (02) : 1 - 10
  • [22] Distinguishing number of hierarchical products of graphs
    Amouzegar, Tayyebeh
    BULLETIN DES SCIENCES MATHEMATIQUES, 2021, 168
  • [23] Some remarks on interval colorings of complete tripartite and biregular graphs
    Jing, Puning
    Miao, Zhengke
    Song, Zi-Xia
    DISCRETE APPLIED MATHEMATICS, 2020, 277 : 193 - 197
  • [24] On Vertex-Distinguishing Proper Edge Colorings of Graphs Satisfying the Ore Condition
    Chen, Meirun
    Guo, Xiaofeng
    ARS COMBINATORIA, 2010, 97 : 377 - 382
  • [25] Edge-colorings of complete graphs that avoid polychromatic trees
    Jiang, T
    West, DB
    DISCRETE MATHEMATICS, 2004, 274 (1-3) : 137 - 145
  • [26] Decomposition of cartesian products of regular graphs into isomorphic trees
    Jao, Kyle F.
    Kostochka, Alexandr V.
    West, Douglas B.
    JOURNAL OF COMBINATORICS, 2013, 4 (04) : 469 - 490
  • [27] Interval edge-colorings of complete graphs and n-dimensional cubes
    Petrosyan, P. A.
    DISCRETE MATHEMATICS, 2010, 310 (10-11) : 1580 - 1587
  • [28] Harmonious Colorings of Graphs
    Byers, Alexis
    Adams, Alyssa
    Calderon, Erica Bajo
    Bindas, Olivia
    Cope, Madeline
    Summers, Andrew
    Thapa, Rabin
    COMBINATORICS, GRAPH THEORY AND COMPUTING, SEICCGTC 2021, 2024, 448 : 223 - 234
  • [29] THE COST OF DISTINGUISHING GRAPHS
    Boutin, Debra
    Imrich, Wilfried
    GROUPS, GRAPHS AND RANDOM WALKS, 2017, 436 : 104 - 119
  • [30] KALEIDOSCOPIC COLORINGS OF GRAPHS
    Chartrand, Gary
    English, Sean
    Zhang, Ping
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2017, 37 (03) : 711 - 727
12345