Questions tagged [regular-graph]
The regular-graph tag has no summary.
21 questions
1
vote
0
answers
85
views
Does a cycle plus triangles graph have a compatible cycle decomposition?
Let $G$ be a 4-regular graph that can be decomposed as a Hamiltonian cycle and triangles. Does it always have a cycle decomposition that is compatible with the cycle plus triangles decomposition? Two ...
- 61
1
vote
1
answer
145
views
Complete graph intersections on a regular polygon
The question concerns complete graphs but for regular polygons. In general, complete graphs are found in graph theory and the definitions do not include metric geometry. However as one can see for ...
- 907
2
votes
1
answer
164
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 ...
- 149
3
votes
1
answer
276
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\...
0
votes
0
answers
102
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 ...
- 269
2
votes
2
answers
204
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 ...
- 14.3k
1
vote
0
answers
184
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$...
- 111
2
votes
1
answer
562
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 ...
1
vote
1
answer
245
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 ...
- 701
5
votes
0
answers
198
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.
...
- 14.8k
2
votes
1
answer
536
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 ...
- 361
3
votes
0
answers
158
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 ...
- 361
2
votes
1
answer
610
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 ...
- 201
5
votes
2
answers
1k
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 ...
- 169
3
votes
2
answers
630
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 ...
- 131