Search

A signed graph Γ = (G , σ) is obtained from a simple graph G by assigning to each edge of G a sign + or −. Let A (Γ) denote the adjacency matrix of Γ and α (G) be the independence number of G. We study the rank of A (Γ) and the independence number α (G) . We show that r (Γ) + 2 α (G) ≥ 2 n - 2 d (G) , where n is the order of G and d(G) is the dimension of the cycle space of G. Moreover, we obtain sharp lower bounds for r (Γ) + α (G) , r (Γ) - α (G) , r (Γ) / α (G) and we characterize all corresponding extremal graphs. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a simple graph with $$n$$ vertices and $$G^c$$ be its complement. The matrix $$Q(G) = D(G) + A(G)$$ is called the signless Laplacian of $$G$$ , where $$D(G) = {\text {diag}}(d(v_1), d(v_2),..., d(v_n))$$ and $$A(G)$$ denote the diagonal matrix of vertex degrees and the adjacency matrix of $$G$$ , respectively. Let $$q_1(G)$$ be the largest eigenvalue of $$Q(G)$$ . We first give some upper and lower bounds on $$q_1(G)+q_1(G^c)$$ for a graph $$G$$ . Finally, lower and upper bounds are obtained for the clique number $$\omega (G)$$ and the independence number $$\alpha (G)$$ , in terms of the eigenvalues of the signless Laplacian matrix of a graph $$G$$ . [ABSTRACT FROM AUTHOR]