Remarks on the critical graph conjecture |
| |
Authors: | I. Broere C.M. Mynhardt |
| |
Affiliation: | Rand Afrikaans University, Johannesburg, Republic of South Africa;University of Pretoria, Pretoria, Republic of South Africa |
| |
Abstract: | The vertex-critical graph conjecture (critical graph conjecture respectively) states that every vertex-critical (critical) graph has an odd number of vertices. In this note we prove that if G is a critical graph of even order, then G has at least three vertices of less-than-maximum valency. In addition, if G is a 3-critical multigraph of smallest even order, then G is simple and has no triangles. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|