**3**

votes

**2**answers

223 views

### Can the Vertices of cubic graph be partitioned into and induced cycle and a forest?

Let $G$ be a $2$-connected $3$-regular graph. Can $V(G)$ be partitioned into $V_1$ and $V_2$ where
$G[V_1]$(the induced subgraph on $V_1$) is a cycle of $G$ and $G[V_2]$ is a forest (Acyclic ...

**2**

votes

**1**answer

137 views

### Is the set of edge of a cubic graph the union of a cycle and and an Acyclic graph?

Let $G$ be a $2$-connected $3$-regular graph. Is it true that $E(G) = E_1 \cup E_2$ where
$G[E_1]$(the induced subgraph on $E_1$) is a cycle of $G$ and $G[E_2]$ is a forest (Acyclic subgraph) of $G$?
...

**2**

votes

**0**answers

79 views

### Counting regular Hypergraphs

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). ...

**0**

votes

**1**answer

78 views

### Topological Irreducible graphs for the projective plane

I learned that there are 103 topological irreducible graphs for the projective plane but I am unable to find examples of said graphs. I am unsure of how to find them on my own and I would like to see ...

**4**

votes

**1**answer

107 views

### Counting the number of $(d_v,d_c)$ regular bipartite graphs

I am trying to count the number of $(d_v,d_c)$ regular bipartite graphs. To be specific, let $n,m,d_v,d_c$ be positive integers such that
$$n\times d_v=m\times d_c.$$
Then, what is the number of ...

**2**

votes

**1**answer

179 views

### Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...

**3**

votes

**1**answer

203 views

### Expected Value for a Connected Graph

Consider a connected graph of N nodes.
Assign randomly to each node a distinct number from 1 to N.
For each node consider the maximum adjacent value or itself if all adjacent values are smaller.
...

**1**

vote

**0**answers

126 views

### A connection between nonplanar complete graphs and the alternating group?

I didn't get any response on MSE so I though I'd give this a try here (my question on MSE).
I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...

**2**

votes

**1**answer

161 views

### Graph of Grassmannian

Let p be an integer, and let G be the graph $(V=Gr(k,\mathbb{F}_q ^n),E)$
where: $Gr(k,\mathbb{F}_q ^n)$ is the set of all subspace of $\mathbb{F}_q$ of dimension k, and $E=\{ W_1,W_2 \in V | ...

**5**

votes

**1**answer

245 views

### A new question about maximal independent sets in regular graphs

This is a question inspired by "A question about independent set in regular graphs".
Suppose that $G$ is a simple $r$-regular graph with $n$ vertices.
We say $H$ is a dominating set for $T$, if
for ...

**11**

votes

**2**answers

360 views

### Strongly connected directed graphs with large directed diameter and small undirected diameter?

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of ...

**6**

votes

**0**answers

135 views

### Uniformly sampling from the set of all simplicial maps

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.
How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial ...

**0**

votes

**1**answer

76 views

### Basis of Cycle Subspace of a Graph

Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles(circuits) of $G$ containing the edge $e$.
For what set of edges does $\mathcal{C_e}$ contain a ...

**-1**

votes

**2**answers

142 views

### spanning tree of a graph of minimum degree three

Does each graph of minimum degree three admit a spanning tree whose vertices have degree three (exactly) except the leaves (degree one)?

**3**

votes

**1**answer

146 views

### Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph

It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard.
By Smith's theorem, ...

**0**

votes

**1**answer

217 views

### A question about independent set in regular graphs

Suppose that $G$ is a simple $r$-regular graph with $n$ vertices.
We say $H$ is a dominating set for $T$, if
for every vertex $v\in T$, we have $v\in H$ or there is a vertex $u\in H$ such that $vu\in ...

**4**

votes

**1**answer

227 views

### Fundamental Cycles of a graphs

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.
Now ...

**1**

vote

**0**answers

135 views

### Can assigment of Cayley graphs be functorial?

Let $G$ and $G'$ be finitely generated groups and $f:G\to G'$ a homomorphism. First question: for a given $f:G\to G'$ it possible to select generating sets $S\in G, S'\in G'$ so that their would be a ...

**2**

votes

**1**answer

149 views

### Labeling vertices in a graph

Is there an efficient algorithm for the following task?:
Given a graph $G$, either find a labelling of vertices with bit strings of length $k$ such
that the labels of adjacent vertices differ in ...

**2**

votes

**2**answers

213 views

### Does this graph have a name?

Let $G$ be a connected graph on $n$ vertices and $\mathcal{T}$ be the set of all spanning trees of $G$.
Consider the graph whose vertices are the elements of $\mathcal{T}$
and
$T, T' \in ...

**5**

votes

**1**answer

180 views

### Paley graphs over $p^{2}$ vertices

I have proved that every Paley graph $P(p^{2})$ over $p^{2}$ vertices, where $p\geq 5$ is a prime number has a cospectral mate, i.e. for every prime number $p\geq 5$ there exists a graph $\Gamma_{p}$ ...

**7**

votes

**1**answer

227 views

### Shortest Paths in the “Cantor Graph”

First, let me explain, what I understand by a "Cantor Graph":
it is an infinite, directed graph with self loops and countably many vertices labelled with the natural numbers; every ordered pair of ...

**2**

votes

**0**answers

82 views

### Hamiltonian Matroids

Similar to graphs, a Matroid $M$ is said to be Hamiltonian if there is a base $B$ of $M$ and $e \in M-B$ such that $B + e$ is a cycle of $M$. Is there any literature on this?
EDIT: Actually my ...

**7**

votes

**0**answers

182 views

### Coherence between different ranking methods of a graph's vertices

Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.
Two natural ways of doing it are:
By the degrees.
By the entries in a ...

**0**

votes

**1**answer

146 views

### Expected length of the shortest polygonal chain connecting N random points in the unit square

N points are selected uniformly at random in the unit square. Let L(N) be the expected length of the shortest (possibly self-intersecting) polygonal chain connecting all the points. It can be proved ...

**3**

votes

**3**answers

338 views

### random networks and prime numbers

I have been studying networks recently and accidentally came up with an heuristic approach towards the distribution of prime numbers. The prime number theorem states that
$\pi(n)\sim n/log(n)$ for ...

**5**

votes

**1**answer

187 views

### Extremal functions for tournaments

We are looking at directed graphs with no loops or parallel edges, but given two vertices $x$ and $y$, we allow the presence of both the edge $(x, y)$ and $(y, x)$. Thus, if $G$ is a directed graph ...

**3**

votes

**1**answer

178 views

### Correspondence between spanning Trees and Even Subgraphs in a Graph

Let $G$ be a connected graph and $T$ a spanning tree of $G$. For $e \in E(G) - E(T)$, Let $C_{e}$ denote the unique cycle in $T + e$.
Let $H(T)$ be the the subgraph of $G$ induced by symmetric ...

**4**

votes

**2**answers

123 views

### Less general edge reconstruction problem for simple graphs

Let $G$ be a simple graph. Let $E^-(G)$ denote the set of (isomorphism classes) of subgraphs of $G$ that can be obtained by deleting a single edge of $G$. Similarly, let $E^+(G)$ be the set of ...

**2**

votes

**0**answers

128 views

### If two graphs have same Laplacian spectrums, are they the similar graphs?

If graph A and graph B have exactly the same Laplacian spectrums, can I just say they are same graphs? (only with scaling edge weights and node index reordering) I don't know if there is any explicit ...

**3**

votes

**1**answer

204 views

### Geodesic convex hulls in a graph; and their properties

This question asks for an analog of the convex hull in a graph that parallels
(as far as possible) convex sets in Euclidean space.
Let $G$ be a simple, undirected graph, and let $S \subseteq V$ be a ...

**3**

votes

**0**answers

68 views

### Size of b-matching constructed from b maximal matchings

The Question: Let $G$ be a (simple) graph and let $b\in\mathbb{N}$. Suppose that we have $b$ disjoint edge-subsets $M_1,\ldots , M_b$ satisfying the following condition: The set $M_1$ is a maximal ...

**6**

votes

**1**answer

213 views

### What is the status of this strong form of Hedetniemi's conjecture?

In this question, a graph is a finite, undirected graph without loops or multiple edges, and a colouring of a graph is a proper vertex colouring. The product $G \times H$ of graphs $G$ and $H$ is the ...

**10**

votes

**1**answer

309 views

### Coloring $K_n$ via edge-weight sums

This is a question inspired by
and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly
much easier!
Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each
edge ...

**3**

votes

**2**answers

186 views

### Two graph constructions: new, old?

Let $G=(V,E)$ be a simple, undirected graph. Let $|V(G)|=n$ and $|E(G)|=m$.
We consider connected graphs only. We write $i\sim j$ if $i$ and $j$ form an
edge. Let $N(i)=\{j:i\sim j\}$. We write ...

**16**

votes

**1**answer

571 views

### A Question on 1, 2 ,3 Conjecture

1, 2, 3 conjecture is well-known:
If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers ...

**1**

vote

**1**answer

103 views

### Proper name for hypergrid or subdivided hypercube?

Is there a name for a graph very similar to a hypercube, but generalized from $2^d$ vertices to $k^d$? Alternatively, similar to a 2-dimensional grid, but generalized to higher dimensions?
In 2 ...

**0**

votes

**0**answers

39 views

### Edge versus vertex assignment in graphs and convex relaxtions

Consider a graph $G = (V,E)$. Let $x \in \{-1,1\}^V$ be a label assignment to vertices of the graph and $z \in \{-1,1\}^E$ be a label assignment to edges of the graph. We say that $z$ is compatible ...

**4**

votes

**0**answers

147 views

### Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset S of the xy-plane is star-convex if there is ...

**0**

votes

**3**answers

414 views

### Stationary distribution for bipartite graph

I was wondering if there is any stationary distribution for bipartite graph? Can we apply random walks on bipartite graph? since we know the stationary distribution can be found from Markov chain, but ...

**4**

votes

**3**answers

160 views

### Tracking automorphism groups of graph processes

Start with an edgeless graph on $n$ labeled vertices, and note that the automorphism group is $\Sigma_n$, the symmetric group on $n$ elements. Now imagine that we randomly start throwing in all of the ...

**0**

votes

**1**answer

92 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**0**

votes

**0**answers

65 views

### Minimum cut in near complete graph

I have a problem with an algorithm that i don't quite understand. The mathematics are not the problem, but I don't understand how it can work in practice. The problem is in the paper ...

**2**

votes

**1**answer

90 views

### Achieving the largest possible minimum spacing between vertices of the same color in an integer lattice

Consider an infinite integer lattice, or an infinite hexagonal lattice with unit length edges. Provided a set of $k$ possible vertex colors, is there a known largest possible minimum spacing that can ...

**6**

votes

**2**answers

389 views

### Is there an algorithm to compute efficiently the dessin d'enfant from a Belyi pair?

Let $(X,f)$ be a Belyi pair, i.e. a Riemann surface $X$ together with a morphism $f: X \to \mathbb{P}^1$, ramified only in $0,1, \infty$. Grothendieck's dessin d'enfant is the pre-image $G$ of the ...

**3**

votes

**1**answer

149 views

### an interesting conjecture about Hamiltonian cycle

Let G be a simple graph which is a cycle $C$ equipped with some chords such that $\delta (G)\geq 3$,in other words,every vertex of $C$ is adjacent with at least one of the chords.
I conjecture that ...

**0**

votes

**1**answer

122 views

### Union of perfect matchings in bridgeless cubic graphs

It's known that every cubic bridgeless graph has 1-factor (Petersen). But Does anybody know, how to prove that for every edge in a cubic bridgeless graph there exists a 1-factor, which contains it?
...

**0**

votes

**0**answers

55 views

### Maximum Independent set of sparse graphs with few triangles

Notations used
$\alpha(G) = $ Max sized independent set of graph $G$.
$n(G) = $ Number of vertex in graph $G$.
Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being ...

**1**

vote

**0**answers

41 views

### complexity of in-dominating set

Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than (n-2)/4, in particular)? I'm mainly looking for the reference.
Thanks for any answer!

**1**

vote

**2**answers

208 views

### Discrete Laplace operator and its eigenvalues

I wonder is there any geometric interpretation of the eigenvalues of the discrete Laplace operator on graphs? Maybe there is a relationship between the eigenvalues and combinatorial properties of ...