**3**

votes

**1**answer

378 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

105 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

310 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

414 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

468 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

126 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

124 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

161 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

228 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

377 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

179 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

448 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

134 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

235 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

251 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

100 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

147 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

96 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

262 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

107 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

129 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

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

**11**

votes

**7**answers

420 views

### Does the notion of graphs with vertex multiplicity exist?

I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have.
It is actually a way to write in a ...

**1**

vote

**1**answer

97 views

### Converse of Petersen's 2-Factorization Theorem

Definition: A $k$-factor of a graph is a spanning $k$-regular
subgraph.
Definition: A $k$-factorization of a graph is a partition of the edge
set into $k$-factors.
Petersen's celebrated ...

**2**

votes

**0**answers

100 views

### Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas.
In the following all graphs are simple and connected.
Let $G$ be graph with vertex set ...

**21**

votes

**3**answers

1k views

### Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...

**8**

votes

**1**answer

183 views

### What is the relationship between the bramble number and the strict bramble number of a graph?

A bramble in a graph $G$ is a set of connected subgraphs $H_1, \dots, H_m$ such that for every $i, j$, either $H_i$ intersects $H_j$ in a vertex, or there exists an edge of $G$ with one end in ...

**2**

votes

**1**answer

131 views

### On cycles in self-centered graphs

Let $G$ be (connected) self-centered graph, i.e. $r(G)=d(G)=m<\infty$.
My question is following
Does $G$ always contains $C_{2m}$ or $C_{2m+1}$ as a subgraph?

**1**

vote

**1**answer

246 views

### Self-containing graphs

[Second try, after this question failed.]
Let me sketch a notion of self-containing structures by a simple example. Consider the class $\Gamma$ of finite or countable digraphs ("graphs" for short) ...

**2**

votes

**0**answers

90 views

### What are the best bounds to date on the maximum girth of a cubic graph?

The girth of a graph is the length of its smallest cycle. Studying the maximum possible girth for a $k$-regular graph on $n$ vertices is a very well-studied problem.
In the 1988 paper "Ramanujan ...

**3**

votes

**4**answers

196 views

### What is the independence number of hamming graph?

Hamming graph H(d,q) is Cartesian product of d complete graphs Kq. We know the independence number of direct product of d complete graphs Kq. What is the independence number of hamming graph?