Efficient algorithms for (3, 1) graphs |
| |
Authors: | Ann Marie Walsh Walter A Burkhard |
| |
Affiliation: | Computer Science Division, Department of Applied Physics and Information Science, University of California, San Diego, La Jolla, California 92093 USA |
| |
Abstract: | In this paper, we define a class of graphs which are referred to as (3, 1) graphs. A graph is a member of this class if it has the property that within each set of three vertices, there is at least one edge. We derive a lower bound for the size of a maximum clique in a (3, 1) graph as well as an upper bound for the size of a minimum clique covering. In addition, we show that there exists a linear algorithm for constructing a Hamiltonian circuit in a connected (3, 1) graph and an n4-algorithm for finding a minimum coloring in a (3, 1) graph. |
| |
Keywords: | graph circuits cliques polynomial-time algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|