Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs |
| |
Authors: | Terry A McKee |
| |
Institution: | Department of Mathematics and Statistics, Wright State University, Dayton, OH 45435-0001, USA |
| |
Abstract: | Robert E. Jamison characterized chordal graphs by the edge set of every k-cycle being the symmetric difference of k−2 triangles. Strongly chordal (and chordal bipartite) graphs can be similarly characterized in terms of the distribution of triangles (respectively, quadrilaterals). These results motivate a definition of ‘strongly chordal bipartite graphs’, forming a class intermediate between bipartite interval graphs and chordal bipartite graphs. |
| |
Keywords: | Chordal graphs Chordal bipartite graphs Strongly chordal graphs Bipartite interval graphs |
本文献已被 ScienceDirect 等数据库收录! |
|