Questions tagged [regular-graph]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
0answers
83 views

Chromatic number of regular graphs using spectra

There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together ...
0
votes
1answer
76 views

Decomposition of regular graphs

Let $G$ be a regular simple graph with degree $\Delta=n-k-1$ and order $m$. Let $C_k$ be the regular graph which is formed by removing a $k$-factor from the complete graph $K_{n}$. I think we could ...
1
vote
1answer
86 views

Lower bound for $\vert \det A \vert $ for the adjacency matrix of regular graphs

Assume $G$ is a simple $k$-regular graph of order $n$ with adjacency matrix $A$ which is non-singular. Does anyone know some lower bounds for $\vert \det (A) \vert$ with respect to $n$, $k$ or both? ...
0
votes
0answers
63 views

The diameter of random regular graphs

In 1982, B. Bollobas and Vega in the paper gave the configurational model to generate $r$-regular random graphs. They gave the following theorem (Theorem 1 in the paper). Theorem: Let $r\geq 3$ and $\...