Journal article
2-Role assignments on triangulated graphs
Theoretical computer science, v 304(01-03), pp 201-214
28 Jul 2003
Abstract
If G is a graph, a k-role assignment is a function mapping each vertex into a role, a positive integer 1,2,…,k, so that if x and y have the same role, then the sets of roles assigned to their neighbors are the same. A graph is called a triangulated graph if it contains no chord-less cycle of four or more vertices. One interesting type of triangulated graph is the indifference graph, that is a graph for which we can find a function on its vertex set so that if x and y are adjacent, then their assigned function values are close. We study 2-role assignments for triangulated graphs. We provide a “greedy” algorithm for finding a 2-role assignment on a connected, non-bipartite triangulated graph with at most one pendant vertex. We characterize indifference graphs that have a 2-role assignment.
Metrics
Details
- Title
- 2-Role assignments on triangulated graphs
- Creators
- Li Sheng - Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA 19104, USA
- Publication Details
- Theoretical computer science, v 304(01-03), pp 201-214
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000184305300009
- Scopus ID
- 2-s2.0-0037811199
- Other Identifier
- 991014878006804721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Theory & Methods