Article ID Journal Published Year Pages File Type
6872387 Discrete Applied Mathematics 2014 6 Pages PDF
Abstract
Let G=(V,E) be a simple graph with vertex set V and edge set E. The rank of G, written as r, is defined to be the rank of its adjacency matrix. Let c denote e−v+θ, where e=|E|, v=|V| and θ means the number of connected components of G, and let m,α,χ′ respectively be the matching number, the independence number, and the chromatic index of G. In this paper, it is proved that ⌈r−c2⌉≤m≤⌊r+2c2⌋, ⌈2er+2c⌉≤χ′, and v−⌊r2⌋−c≤α≤v−⌈r2⌉. Examples are given to show that all the bounds can be attained.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,