On detectable colorings of graphs

Henry Escuadro; Ping Zhang

Mathematica Bohemica (2005)

  • Volume: 130, Issue: 4, page 427-445
  • ISSN: 0862-7959

Abstract

top
Let G be a connected graph of order n ≥ 3 and let c E ( G ) → { 1 , 2 , ... , k } be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G , the color code of v with respect to c is the k -tuple c ( v ) = ( a 1 , a 2 , ⋯ , a k ) , where a i is the number of edges incident with v that are colored i ( 1 ≤ i ≤ k ). The coloring c is detectable if distinct vertices have distinct color codes. The detection number det ( G ) of G is the minimum positive integer k for which G has a detectable k -coloring. We establish a formula for the detection number of a path in terms of its order. For each integer n ≥ 3 , let D u ( n ) be the maximum detection number among all unicyclic graphs of order n and d u ( n ) the minimum detection number among all unicyclic graphs of order n . The numbers D u ( n ) and d u ( n ) are determined for all integers n ≥ 3 . Furthermore, it is shown that for integers k ≥ 2 and n ≥ 3 , there exists a unicyclic graph G of order n having det ( G ) = k if and only if d u ( n ) ≤ k ≤ D u ( n ) .

How to cite

top

Escuadro, Henry, and Zhang, Ping. "On detectable colorings of graphs." Mathematica Bohemica 130.4 (2005): 427-445. <http://eudml.org/doc/249588>.

@article{Escuadro2005,
abstract = {Let $G$ be a connected graph of order $n \ge 3$ and let $c\: E(G) \rightarrow \lbrace 1, 2, \ldots , k\rbrace $ be a coloring of the edges of $G$ (where adjacent edges may be colored the same). For each vertex $v$ of $G$, the color code of $v$ with respect to $c$ is the $k$-tuple $c(v) = (a_1, a_2, \cdots , a_k)$, where $a_i$ is the number of edges incident with $v$ that are colored $i$ ($1 \le i \le k$). The coloring $c$ is detectable if distinct vertices have distinct color codes. The detection number $\det (G)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable $k$-coloring. We establish a formula for the detection number of a path in terms of its order. For each integer $n \ge 3$, let $D_u(n)$ be the maximum detection number among all unicyclic graphs of order $n$ and $d_u(n)$ the minimum detection number among all unicyclic graphs of order $n$. The numbers $D_u(n)$ and $d_u(n)$ are determined for all integers $n \ge 3$. Furthermore, it is shown that for integers $k \ge 2$ and $n \ge 3$, there exists a unicyclic graph $G$ of order $n$ having $\det (G)=k$ if and only if $d_u(n) \le k \le D_u(n)$.},
author = {Escuadro, Henry, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {detectable coloring; detection number; unicyclic graph; detection number; unicyclic graph},
language = {eng},
number = {4},
pages = {427-445},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On detectable colorings of graphs},
url = {http://eudml.org/doc/249588},
volume = {130},
year = {2005},
}

TY - JOUR
AU - Escuadro, Henry
AU - Zhang, Ping
TI - On detectable colorings of graphs
JO - Mathematica Bohemica
PY - 2005
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 130
IS - 4
SP - 427
EP - 445
AB - Let $G$ be a connected graph of order $n \ge 3$ and let $c\: E(G) \rightarrow \lbrace 1, 2, \ldots , k\rbrace $ be a coloring of the edges of $G$ (where adjacent edges may be colored the same). For each vertex $v$ of $G$, the color code of $v$ with respect to $c$ is the $k$-tuple $c(v) = (a_1, a_2, \cdots , a_k)$, where $a_i$ is the number of edges incident with $v$ that are colored $i$ ($1 \le i \le k$). The coloring $c$ is detectable if distinct vertices have distinct color codes. The detection number $\det (G)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable $k$-coloring. We establish a formula for the detection number of a path in terms of its order. For each integer $n \ge 3$, let $D_u(n)$ be the maximum detection number among all unicyclic graphs of order $n$ and $d_u(n)$ the minimum detection number among all unicyclic graphs of order $n$. The numbers $D_u(n)$ and $d_u(n)$ are determined for all integers $n \ge 3$. Furthermore, it is shown that for integers $k \ge 2$ and $n \ge 3$, there exists a unicyclic graph $G$ of order $n$ having $\det (G)=k$ if and only if $d_u(n) \le k \le D_u(n)$.
LA - eng
KW - detectable coloring; detection number; unicyclic graph; detection number; unicyclic graph
UR - http://eudml.org/doc/249588
ER -

References

top
  1. Irregular assignments and two problems á la Ringel. Topics in Combinatorics and Graph Theory. (R. Bodendiek and R. Henn, eds.), Physica, Heidelberg (1990), 29–36. (1990) MR1100017
  2. Irregular assignments and vertex-distinguishing edge-colorings of graphs, Combinatorics ’90, Proc. Conf., Gaeta/Italy 1990, Elsevier Science Pub., New York (1992), 1–9. (1992) MR1195794
  3. On graphs with irregular coloring number 2 , Congr. Numerantium 100 (1994), 129–140. (1994) Zbl0836.05029MR1382313
  4. 10.1016/0012-365X(93)E0225-S, Discrete Math. 141 (1995), 279–283. (1995) Zbl0829.05027MR1336691DOI10.1016/0012-365X(93)E0225-S
  5. Detectable colorings of graphs, (to appear). (to appear) MR2212794
  6. Introduction to Graph Theory, McGraw-Hill, Boston, 2005. (2005) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.