Some relations between rank, chromatic number and energy of graphs

DOI10.1016/J.DISC.2008.09.012zbMATH Open1194.05075arXiv0709.3140OpenAlexW2039492976MaRDI QIDQ1011502FDOQ1011502

S. Akbari, S. Zare, E. Ghorbani

Publication date: 8 April 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The energy of a graph $G$, denoted by $E(G)$, is defined as the sum of the absolute values of all eigenvalues of $G$. Let $G$ be a graph of order $n$ and $mrank(G)$ be the rank of the adjacency matrix of $G$. In this paper we characterize all graphs with $E(G)=mrank(G)$. Among other results we show that apart from a few families of graphs, $$, where $n$ is the number of vertices of $G$, $$ and $chi(G)$ are the complement and the chromatic number of $G$, respectively. Moreover some new lower bounds for $E(G)$ in terms of $mrank(G)$ are given.

Full work available at URL: https://arxiv.org/abs/0709.3140

zbMATH Keywords

energyrankchromatic number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recent results in the theory of graph spectra
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• On Complementary Graphs
• The energy of a graph
• Polygonal chains with minimal energy
• Energy ordering of catacondensed hexagonal systems
• On the minimal energy of trees with a given diameter

Cited In (16)

• Choice number and energy of graphs
• Energy, matching number and odd cycles of graphs
• Lower bounds of graph energy in terms of matching number
• Some relations among term rank, clique number and list chromatic number of a graph
• Remarks on the bounds of graph energy in terms of vertex cover number or matching number
• Rank, term rank and chromatic number of a graph
• Relation between the skew energy of an oriented graph and its matching number
• Generating new test instances by evolving in instance space
• Some lower bounds for the energy of graphs in terms of spread of matrix
• Upper bound of skew energy of an oriented graph in terms of its skew rank
• Bounds of graph energy in terms of vertex cover number
• Upper bounds of the energy of triangle-free graphs in terms of matching number
• On the Energy of Graphs
• On bounds for the energy of graphs and digraphs
• The bounds of the energy and Laplacian energy of chain graphs
• Energies of Hypergraphs

Uses Software

• GRAFFITI

This page was built for publication: Some relations between rank, chromatic number and energy of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1011502)