✦ LIBER ✦

A characterization of uniquely vertex colorable graphs using minimal defining sets

✍ Scribed by H. Hajiabolhassan; M.L. Mehrabadi; R. Tusserkani; M. Zaker

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 267 KB
Volume: 199
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(98)00304-5

No coin nor oath required. For personal study only.

✦ Synopsis

A defining set (sf cute-x coloring) of a graph G is a set of vertices S with an assignment of colors to its elements which has a unique completion to a proper coloring of G. We define a minimal d&kg set to be a defining set which does not properly contain another defining set. If G is a uniquely vertex colorable graph, clearly its minimum defining sets are of size x(G)-I. It is shown that for a coloring of G, if all minimal defining sets of G are of size x(G)-I, then G is a uniquely vertex colorable graph.

📜 SIMILAR VOLUMES

Defining sets in vertex colorings of gra

Defining sets in vertex colorings of graphs and latin rectangles

✍ E.S. Mahmoodian; Reza Naserasr; Manouchehr Zaker 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 410 KB

In a given graph G, a set of vertices S with an assignment of colors is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a z(G)coloring of the vertices of G. The concept of a defining set has been studied, to some extent, for block desig

Determination of all minimal cut-sets be

Determination of all minimal cut-sets between a Vertex pair in an undirected graph : U. Abel and R. Bicker. IEEE Trans. Reliab.R-31 (2), 167 (1982)

📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 113 KB