Characterizations of 2-variegated graphs and of 3-variegated graphs |
| |
Authors: | Vasanti N Bhat-Nayak SA Choudum Ranjan N Naik |
| |
Institution: | Centre of Advanced Study in Mathematics, University of Bombay, Bombay 400 098, India;Department of Mathematics, University of Bombay, Bombay 400 098, India |
| |
Abstract: | A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. We prove that a graph G on 2n vertices is 2-variegated if and only if there exists a set S of n independent edges in G such that no cycle in G contains an odd number of edges from S. We also characterize 3-variegated graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|