Skip to main content

Questions tagged [regular-graph]

Filter by
Sorted by
Tagged with
2 votes
1 answer
135 views

Prove $G$ is regular if $d(u, v)$ is $x$ for adjacent $u$ and $v$ and is $y \ge 2$ otherwise

Prove $G$ is regular if $d(u, v)$ is $x$ for adjacent $u$ and $v$ and is $y \ge 2$ otherwise. Here $d(u, v)$ denotes the number of common adjacent vertices between $u$ and $v$. PS: I've been working ...
Nima Aryan's user avatar
3 votes
1 answer
228 views

Are "ultra-regular" bipartite graphs complete?

Let $X, Y$ be non-empty, disjoint sets and let $R\subseteq X\times Y$ be a binary relation. For $x\in X$, we set $R(x) = \{y\in Y: (x,y) \in R\}$ and for $y\in Y$, let $R^{-1}(y) = \{x\in X:(x,y)\in R\...
Dominic van der Zypen's user avatar
0 votes
0 answers
57 views

A question related to contiguity of random regular graphs

I am looking for a reference for the following fact. Let $r\geq 3$ be constant, let $G(n,r-2)$ be a random (simple) $(r-2)$-regular graph and let $H(n)$ be an independent random Hamiltonian cycle (on ...
35T41's user avatar
  • 143
2 votes
2 answers
123 views

Existence of certain regular graphs

Question: what can be said about the existence of $2k$ regular graphs, $1\lt k$ that have a $1$-factor and a $2$-factor? Provided their existence, what is/are the smallest for $k$? The graphs must be ...
Manfred Weis's user avatar
  • 13.2k
1 vote
0 answers
132 views

Random graphs constructed by many large matchings

Let $G_{n,d}$ be $d$-regular random graph. We know that for $d \geq 3$, $G \in G_{n,d}$ a.a.s. has a $1$-factorisation when $n$ is even. So, the resulting graph that obtained from randomly choosing $d$...
Yuhang Bai's user avatar
1 vote
1 answer
366 views

Tree width and clique width of regular graphs

Consider a $k$ regular graph of $n$ vertices, where $3 \leq k \leq (n-1)$. Is there any upper or lower bound, in the worst case, known for either the tree-width or the clique width of each $k$ regular ...
RandomMatrices's user avatar
1 vote
1 answer
187 views

Deleting vertices of a regular graph to obtain a regular graph

Let $G$ be a symmetric $n$-regular graph. For which $k$ it is possible to delete some vertices from $G$ to obtain $k$-regular graph $G'$? For example, if $G$ is icosahedral graph (i.e. $5$-regular ...
Fedor Nilov's user avatar
5 votes
0 answers
154 views

How to construct 4-regular graphs with few Hamiltonian decompositions?

A Hamiltonian decomposition of a finite simple graph is a partition of its edge set so that each partition class forms a Hamiltonian cycle. This is only possible if the graph is $2k$-regular. ...
M. Winter's user avatar
  • 13.6k
2 votes
1 answer
391 views

Maximum number of leaf blocks in 3-regular (cubic) graph

The definition of block is Block of $G$ is a maximal subgraph $G'$ of $G$ with no cut vertex of $G'$ itself. Of course, there can exist many blocks in $G$. In particular, isolated vertices, edges in ...
okw1124's user avatar
  • 341
3 votes
0 answers
99 views

If the girth of a $2k$-regular graph $G$ is larger than the diameter of a tree $T$ with $k$ edges, then $G$ is decomposed into copies of $T$

I want to prove that ‘If the girth of a $2k$-regular graph $G$ is larger than the diameter of a $k$-edge tree $T$, then $G$ is covered by edge-disjoint copies of $T$.’ I tried several ways to solve ...
okw1124's user avatar
  • 341
2 votes
1 answer
491 views

Is every $k$-edge connected $k$-regular graph Hamiltonian?

A graph $G$ is Hamiltonian if there is a Hamiltonian cycle in $G$. Suppose $G$ is a $k$-edge connected $k$-regular graph with $k>1$. Does this ensure that $G$ is Hamiltonian? If not, how about ...
Cyriac Antony's user avatar
5 votes
2 answers
576 views

Smallest $3$-regular graph with a unique perfect matching

What is the smallest 3-regular graph to have a unique perfect matching? With a large enough number of nodes, it is possible for a 3-regular graph to have no perfect matching (example can be seen in ...
PickupSticks's user avatar
3 votes
2 answers
440 views

Efficiently generating all regular/bidegreed graphs

There is a related question on how to generate all regular graphs; however, the procedure is random and repeats the generated graphs. Plus, there is no stop condition, unless recording the total ...
Sergey Ivanov's user avatar
3 votes
0 answers
154 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 ...
vidyarthi's user avatar
  • 2,089
0 votes
1 answer
157 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 ...
vidyarthi's user avatar
  • 2,089
1 vote
1 answer
171 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? ...
Mohammad Ali Nematollahi's user avatar
0 votes
0 answers
445 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 $\...
Ranveer Singh's user avatar