**0**

votes

**0**answers

60 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

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

**2**

votes

**1**answer

117 views

### Factors of Kneser graph

With respect to the Strong product, is the Kneser graph prime and if not how does one find a prime decomposition? Are there any references or algorithms?

**1**

vote

**2**answers

214 views

### a conjecture about Hamiltonian graph

Suppose $G$ is a simple graph and $V(G)=V(C)\bigcup \{u_1,...,u_n\}$,where $C$ is a $2n$-cycle in $G$ and $V(C)=\{a_1,...,a_n,b_1,...,b_n\}$ such that
$(1)V(C)\bigcap \{u_1,...,u_n\}=\varnothing$;
...

**3**

votes

**1**answer

391 views

### Is there a graph-theoretical proof of Tutte's theorem on matroids?

First of all, I'm not a mathematician and I hope this question isn't too elementary, but I got no answers on math.SE, and since this is a reference request on a relatively advanced theorem, I thought ...

**2**

votes

**0**answers

106 views

### The Turán problem for graphs with given chromatic number

The ordinary Turán problem for graphs asks, "Given a graph $H$, if $G$ is an $H$-free graph on $n$ vertices, what is the largest number of edges that $G$ can have?" As is well known, if $\chi(H) = r ...

**2**

votes

**0**answers

183 views

### On the existence of Graph Monomorphism

A graph monomorphism is an injective graph homomorphism. Determining existence of Graph monomorphism between graph pairs is computationally hard.
Assume we talk only about classes of undirected ...

**5**

votes

**3**answers

312 views

### New trends in Applied Graph Theory [closed]

What are current trends in Applied Graph Theory? I am interested mainly in non-algorithmical problems. Maybe even in applications of graphs to other mathematical disciplines. For example, abstract ...

**2**

votes

**1**answer

155 views

### positive semidefinite matrix condition

There is a great work of Alizadeh that in section 4 speaks about Minimizing sum of the first few(k-largest) eigenvalues of a symmetric matrix. Instead of a symmetric model we use the weighted ...

**5**

votes

**1**answer

415 views

### No big clique minor but a big grid minor

I was wondering if the following result is known (or if there's a nice short proof without treewidth/brenchwidth related theorems): as the title says, suppose you have a graph without a big clique ...

**9**

votes

**2**answers

216 views

### the length of cycles in a $2$-connected simple gragh

Let $G=(V,E)$ be a simple $2$-connected graph and $C$ is a cycle in $G$ satisfies:
For any vertex $v$ of $C$,there exists at least one vertex $u\in V(G)\backslash V(C)$ adjacent with $v$.
Is it true ...

**5**

votes

**2**answers

470 views

### A conjecture about odd path and odd cycle

Let $k$ be a positive integer and $G=(V,E)$ be a $2$-connected simple graph.Suppose $v\in V(G)$ satisfy:
$(1)$there exists at least one vertex $u\in V(G)\backslash\{v\}$ such that $u$ is not adjacent ...

**3**

votes

**1**answer

127 views

### Triangulations of a disk, flip distance and hamiltonian circuit

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior.
Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...

**0**

votes

**0**answers

125 views

### Monotone graph parameters under vertex deletion

Let $f(G)$ denote any parameter of a graph $G$ for which $f(G) \geq f(G - \{v \})$, where $v$ is any vertex in $G$. We could describe such parameters as being monotone under vertex deletion. Does ...

**5**

votes

**0**answers

162 views

### A linear optimization problem on a graph

Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...

**7**

votes

**0**answers

181 views

### Is there a Rado category?

The Rado graph appears to have a nice universality property (it contains all finite and all countably infinite graphs as induced subgraphs) and homogeinety property (any isomorphism between ...

**1**

vote

**0**answers

66 views

### How close to platonic can a non-platonic planar graph be?

Direct question:
Is it possible to construct a finite, planar, $k$-regular graph in which all the faces except one have the same degree (are bounded by a cycle with the same number of edges), and the ...

**2**

votes

**3**answers

230 views

### eigenvalue of Laplacian matrix

If we have a Laplacian matrix $\boldsymbol{A}$ such that
\begin{align}
&A_{ii} >0 \\
&A_{ii}=-\sum_{j\neq i}A_{ij}
\end{align}
with known eigenvalues $\lambda_i$.
Define the matrix ...

**0**

votes

**0**answers

93 views

### Adjacent matrix of undirected graph with a giant component

Assuming there is a undirected random graph $G=(V,E)$, $|V|=N$ and its adjacent matirx is $A$.
What is the sufficient and necessary conditions of A for that there is a giant component of graph $G$?
...

**9**

votes

**2**answers

383 views

### Is the Steiner ratio Gilbert–Pollak conjecture still open?

Gilbert-Pollak conjecture on the Steiner ratio: Consider a set $P$ of $n$ points on the euclidean plane. A shortest
network interconnecting $P$ must be a tree, which is called a Steiner minimum ...

**2**

votes

**1**answer

182 views

### When does graph Laplacian have eigenvalue -1?

Consider an undirected graph $G$ with (symmetric) adjacency matrix $A \in \{0,1\}^{n \times n}$ and degree sequence $d = (d_i)$ where $d_i = \sum_{j} A_{ij}$. Assume that every node has degree at ...

**0**

votes

**1**answer

117 views

### 3-complexes not embeddable in 3-space

My question is about embeddability of 3-dimensional complexes in R^3. Do we have something like Kuratowski's theorem for complexes in 3-space which specifies a set of minors for non-embeddability?

**1**

vote

**0**answers

64 views

### maximum weight k-edge problem

Given positive integer $k$ and an undirected graph $(V,E)$, with nonnegative (non-uniform) weights on the nodes. Find $k$ edges whose spanning nodes have the maximum weight.
Is this in P or NP? I ...

**2**

votes

**0**answers

87 views

### Capacity of Cycle Graphs

Shannon capacity $\Theta(G)$ of pentagon is achieved at $2$-fold strong product of the pentagon.
It is also known that the Lov\'asz theta $\vartheta(G)^m\neq\alpha(G^{\boxtimes m})$ for any finite ...

**9**

votes

**0**answers

160 views

### How many n/2-cycles can a cubic graph have

Given a simple cubic graph with $n$ vertices (which implies that $n$ is even), what is a good upper bound on the number of cycles of length $n/2$ it can have?
A random cubic graph has ...

**7**

votes

**1**answer

439 views

### Separating pairs of points in R^n

Let $A$ be a set of $2k$ points in $\mathbb{R}^n$ such that no open set in $\mathbb{R}^n$ of diameter $2$ contains more than $k$ of these points. What is the largest possible distance $r_n>0$ one ...

**2**

votes

**0**answers

84 views

### Groups of automorphisms of weighted graphs

Let $\Gamma=(V,E,\omega)$ be an (edge-)weighted graph without loops and multiple edges. Here $V$ is the set of vertices, $E$ is the set of edges and $\omega:E \to \mathbb{N}$. A permutation $\varphi$ ...

**5**

votes

**0**answers

451 views

### Does this graph property have a name?

I'm interested in a family of properties of connected simple graphs that comes up in percolation theory.
Let $G$ be a simple connected graph. Now consider the set of subgraphs of $G$ that I will call ...

**4**

votes

**0**answers

137 views

### Graphs with many positive eigenvalues of their distance matrix

Let $G$ be a simple connected graph $D(G)$ its distance matrix and $n_{+}(G), n_{-}(G)$ the number of positive and negative eigenvalues of $D(G)$ respectively.
We call a graph $G$ optimistic if ...

**2**

votes

**1**answer

69 views

### Graphs with polynomial volume growth

Let $G = (V,E)$ a graph, equipped with graph distance (i.e. for $x,y \in V$, the distance $d(x,y)$ is the length of the minimum path connecting $x$ and $y$). For $x \in V$ and $r \in \mathbb N$, ...

**7**

votes

**0**answers

132 views

### Colouring a graph whose edge set is a special union of cliques

I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...

**11**

votes

**0**answers

237 views

### A Ramsey avoidance game

Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...

**5**

votes

**5**answers

254 views

### Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $G$ then we can reduce the finding of a Hamiltonian cycle in $G$ to a Eurler your of $H$ ...

**5**

votes

**1**answer

144 views

### NP-hardness of sparsest cut

Consider bipartitioning the vertices of a graph $(V,E)$ into $V = P \cup Q$ to minimize $$\frac{|E(P,Q)|}{|P| |Q|},$$ where $E(P,Q)$ denotes the set of edges in the cut. The usual citation for ...

**1**

vote

**0**answers

101 views

### Is the automorphism group of a homogeneous (locally finite) tree unimodular?

I have seen somewhere (that I don't remember now) that the (full) automorphism group of a k-regular tree is unimodular. I assume a k-regular tree is the same thing as the homogeneous tree of degree k ...

**3**

votes

**1**answer

149 views

### vertex independent set and the maximal clique

Let $N>2$ be a positive integer and $G$ be a simple graph satisfies:
the maximal degree of $G$ is $N$
the clique number of $G$ is $N$.
I want to ask if there exists a vertex independent set $I$ ...

**2**

votes

**2**answers

180 views

### Partition of $\mathbb{F}_2^n$?

Consider an undirected graph $G$ with $n$ nodes denoted by $i$, $i \in [n] = \{1,2,...,n\}$. Denote the set of neighbours of node $i$ in the graph by $N(i)$.
Given that there exists a set ...

**1**

vote

**0**answers

97 views

### A traveling time problem

Given any undirected, connected and simple graph $G(V,E)$,each node of which is considered as a city. We call $j$ a neighbor of $i$ if $(i,j)\in E$. $N_i$ is the set of neighbors of $i$. $|V|=N$
...

**8**

votes

**1**answer

264 views

### normalized laplacian spectrum of trees

Is it known for which class of graphs the normalized laplacian has only simple eigenvalues (i.e., with multiplicity one)? In particular, are there trees (or perhaps a specific class of trees) whose ...

**2**

votes

**0**answers

51 views

### Upper bound on size of obstruction set for wye-delta-wye reducible graphs

A graph is $Y \Delta Y$-reducible if it can be reduced to an empty graph by the following operations:
$Y \leftrightarrow\Delta$ transforms;
Replacing multiple edges with single edges (parallel ...

**3**

votes

**0**answers

108 views

### Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, ...

**3**

votes

**1**answer

130 views

### the minimum possible value of the order of a graph G which is a finite union of N-order complete graphs

Let $N$ be a positive integer,$G$ be a simple graph and $H_1,H_2,\ldots,H_k$ be a family of subgraphs of $G$ which satisfy:
every $H_i$ is a $N$-order complete graph;
the union of $H_i$ is $G$;
the ...

**3**

votes

**2**answers

244 views

### chromatic number of a simple graph whose length of the longest odd cycle is 2k+1

Let $G$ be a simple graph and the length of the longest odd cycle of $G$ is $2k+1$,then I guess the chromatic number of $G$ is no more than $2k+2$,is it right?

**3**

votes

**1**answer

63 views

### Commensurability of 2-colorings of finite 4-valent graphs

It is quite easy to show that given two finite 4-valent graphs $X,X'$ (I will take the convention that there is at most one edge between two vertices, but allow loops) there is a third such graph ...

**5**

votes

**2**answers

138 views

### Embedding points in 2D based on distance estimates?

Suppose we have a collection of exactly $N$ points (say $N=1000$), with each point belonging to 2-dimensional Euclidean space $\mathbb{R}^2$, but we don't know the coordinates of the points. Suppose ...