**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

358 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

141 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

215 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

226 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

148 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

212 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

179 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

80 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

181 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

337 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

177 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 ...

**3**

votes

**2**answers

108 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

212 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

308 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

570 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

38 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

146 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

407 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

159 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

91 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

89 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

387 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

147 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 ...

**0**

votes

**0**answers

59 views

### Constructing a digraph from its spectrum

This is related to the following question from cs theory stack exchange:
http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem
So it seems as if given a sequence of real ...

**6**

votes

**2**answers

257 views

### What is the maximum of the ratio $\vartheta(G)/\alpha(G)$?

A maximum independent set is a largest independent set for a given graph $G$ and its size is denoted $\alpha(G)$. And the Lovász number of $G$ is denoted $\vartheta(G)$. $\vartheta(G)\geq \alpha(G)$ ...

**2**

votes

**2**answers

125 views

### Name for Kneser/Johnson-like graphs?

I wonder if the following simple generalization of Johnson and Kneser
graphs has a name? Let the vertex set of the graph $G(n,k,t)$ be the
set of $k$-element subsets of an $n$-set, with two $k$-sets ...

**4**

votes

**3**answers

165 views

### Crystal structure, lattice, Graph and coloring

I am working across mathematics, physics and engineering. And I am looking for whether there exists already formally established knowledge in the field.
Given a periodic graph (actually a physical ...

**2**

votes

**3**answers

381 views

### Counting graphs up to isomorphism

I apologize if the questions are too elementary for the forum, but I am not an expert in this fields.
How many (rooted or unrooted) binary trees with $n$ vertices are there up to isomorphism?
How ...

**0**

votes

**1**answer

68 views

### On homomorphisms between vertex transitive graphs

In general there is no relation between automorphism groups of subgraphs and the main graph. However, this question is about vertex transitive graphs.
Given vertex transitive $G$ and $H$ such that ...

**-1**

votes

**1**answer

198 views

### an interesting conjecture about even cycle

Let G be a simple graph which is a $2n$-cycle equipped with $n$ chords such that $G$ is $3$-regular,in other words,the set of the $n$ chords is a perfect matching of $G$(that is,every vertex of $G$ is ...