**6**

votes

**2**answers

178 views

### Find multiple non-adjacent paths in a graph

Consider a non-directed graph. I want to find as many non-adjacent paths as possible from a source $s$ to a destination $t$. Two paths $P_1$ and $P_2$ are said to be non-adjacent to each other if none ...

**4**

votes

**1**answer

116 views

### Product of geodesic distances

I'm working on trying to show this, but can't seem to get started. No guarantees that it is true, but other conditions on the adjacency matrix that make it true or a counter example are helpful. ...

**0**

votes

**2**answers

84 views

### different way of selecting a random graph

Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this ...

**0**

votes

**4**answers

117 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...

**3**

votes

**1**answer

108 views

### Graphs of lines on del Pezzo surfaces

Let $k$ be an algebraically closed field. To any del Pezzo surface $S$ over $k$ we may associate its graph of lines, which has one vertex for each line and an edge (with multiplicity if required) ...

**2**

votes

**1**answer

168 views

### Clique problem for regular graphs

I am looking for NP complete results for cliques in regular graphs. For example is the general problem of determining if a regular graph on n vertices has an n/2 clique NP-complete? (obviously the ...

**0**

votes

**0**answers

47 views

### Paths on Cartesian products of graphs satisfying linear constraints

Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ ...

**1**

vote

**0**answers

73 views

### Empty node in cactus construction

Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph?
In particular is there a necessary condition for not having empty k-junction ...

**0**

votes

**0**answers

46 views

### Correlation between attributes in a binary graph

Given an unrooted binary tree whose leaves are vertices of degree one that are labelled bijectively by a set $S$. We define a categorical attribute $A$ ($|A|<<|S|$) and each leaf is assigned a ...

**1**

vote

**0**answers

112 views

### Find a path that covers as many nodes as possible

I have the following interesting problem. Given a graph $G$, an agent starts to mark nodes in $G$ in the following way: it marks all nodes within distance $d$ from it. Now the question is to find the ...

**4**

votes

**1**answer

144 views

### Expected number of connected components in a random graph

For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value?
I'm specially interested in what happens for small values of p, ...

**-4**

votes

**1**answer

155 views

### Bipartite graph [closed]

First of all, thank you for your time to reading my post.
I am a researcher but not a mathematician, i have some difficulties in solving a math problem, that why i am here to ask your help. I just ...

**0**

votes

**1**answer

161 views

### Kneser graphs eigenvalues

Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...

**6**

votes

**2**answers

202 views

### Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index

Let $\chi'_f(G)$ be the fractional chromatic index.
Based on limited experiments (up to 8 vertices and few larger graphs),
I suspect:
Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = ...

**2**

votes

**1**answer

95 views

### Estimate for the travelling salesman problem for balls inside a grid

This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around...
The question concerns the TSP problem (with ...

**1**

vote

**0**answers

138 views

### random walk with reflecting barriers [closed]

Consider a random walk on the line 1,...,d. You start at point 1. At each step you flip a coin: heads means go left, tails means go right. If you're at 1 and get a heads, just stay where you are (same ...

**5**

votes

**2**answers

250 views

### Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...

**0**

votes

**0**answers

83 views

### Tactics/strategies to win the chip firing game between two-players

Given a connected, undirected graph, two players (black and red) play the following game:
Note: Initially, all vertices do not contain any tokens.
To begin the game, each player (black or red) ...

**0**

votes

**1**answer

87 views

### Finding node-disjoint routes with mutually exclusive nodes in graphs

I have the following problem. I would like to know if it reduces to some standard problem in Graph theory. Particularly, I would like to know whether it is NP-hard, if yes, how to prove its ...

**1**

vote

**0**answers

50 views

### Simulation of disassortative random graphs

Recently I have been trying to find a succinct algorithm for generation of disassortative networks. The best I have found is the algorithm by Newman described in his paper "Mixing patterns in ...

**1**

vote

**0**answers

53 views

### Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there graph problems that can be solved in
...

**3**

votes

**3**answers

313 views

### Turan's theorem for connected graphs?

Using a small modification to Turáns theorem we can find the minimum amount of edges a graph $G$ on $n$ vertices must have so it does not have an independent set of size $k$. Is there a similar result ...

**1**

vote

**0**answers

55 views

### Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...

**6**

votes

**0**answers

137 views

### The Universal Labeling of graph

The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...

**8**

votes

**1**answer

192 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**1**

vote

**1**answer

100 views

### How to model a time-discrete heat equation on a graph?

I would like to know how one can set up a time-discrete model for the heat equation on a graph?
Is this problem using the heat kernel equation on a graph?

**0**

votes

**0**answers

73 views

### Heat equation with graph laplacian

I would like to start with considering the time-dependent heat equation on a connected graph and consider its Laplacian matrix.
Suppose we have a connected graph with unknown temperature on vertices. ...

**0**

votes

**0**answers

72 views

### Eigenvalues of the Cayley-like graph

Let $ F_q $ be a finite field of characteristic 2.
Let $ x^2 + Sx +P \in F_q[x] $ be an irreducible polynomial over $ F_q $,
and let $ g $ be one of its roots in $ F_{q^2} $.
Define a map $ M: ...

**34**

votes

**6**answers

3k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...

**13**

votes

**1**answer

615 views

### Who first dubbed them “expander graphs”?

Expander graphs
("sparse graphs that have strong connectivity properties")
burst onto the mathematical scene around the millennium, but I have not
been successful in tracing the origin of
(a) the ...

**7**

votes

**2**answers

134 views

### Bounds on chromatic number of $k$-planar graphs

A $1$-planar graph can be drawn in the
plane so that each arc is crossed at most once by another arc.
A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times.
Planar graphs are ...

**19**

votes

**0**answers

675 views

### Non-linear expanders?

Recall that a family of graphs (indexed by an infinite set, such as the primes, say) is called an expander family if there is a $\delta>0$ such that, on every graph in the family, the discrete ...

**5**

votes

**1**answer

160 views

### Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.
The famous Nash-Williams conjecture claims ...

**4**

votes

**2**answers

249 views

### Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...

**0**

votes

**1**answer

56 views

### mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.
Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...

**8**

votes

**5**answers

1k views

### Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate ...

**0**

votes

**0**answers

28 views

### number of bipolar orientations to acyclic ones

Given a $k$-regular graph $G$, is there an upper bound on the number of bipolar orientations that $G$ has?
I am trying to show that the number of bipolar orientations is much much lower than the ...

**5**

votes

**0**answers

100 views

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**5**

votes

**0**answers

152 views

### Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?

Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then ...

**3**

votes

**3**answers

162 views

### Examples of graph properties characterized by forbidden (not necessarily induced) subgraphs

A graph property is hereditary if it is closed under taking induced subgraphs (equivalently, if it is closed under removing vertices). A graph property is monotone if it is closed under taking ...

**0**

votes

**0**answers

38 views

### Cycle cover of a cubic polyhedral graph

Tutte graph is a counterexample for the Tait's conjecture stating that all cubic graphs are Hamiltonian. For the non-hamiltonian graphs - is it true that all vertices of any such graph can be covered ...

**2**

votes

**0**answers

48 views

### Regular graphs with unimodal subdegrees that are not distance-regular

Distance regular graphs are known to exhibit the following property: starting from an arbitrary vertex $\alpha$, let $k_i$ denote the number of vertices at distance $i$ from $\alpha$ (in terms of ...

**1**

vote

**0**answers

68 views

### labeling vertices in a graph to minimize distance between adjacent vertices

We have a regular graph $G$ of degree $m$ on $n$ vertices and we label each of its vertices with the number $1$ through $n$. What can we say about the maximum difference between the numbers of two ...

**7**

votes

**2**answers

273 views

### Wait time to grid network disconnection with failing edges

Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node
connected to its four neighbors, with the top row connected to the bottom,
and the right column connected to the left.
Suppose ...

**2**

votes

**0**answers

61 views

### Characterize the equivalence class of bipartite graphs obtained from each other by elementary row operations on their adjacency matrices

Let $M$ be an $m\times n$ matrix real matrix. Let $G$ be a bipartite graph, with partitions $A$ and $B$, such that $|A|=m$ and $|B|=n$. A node $i\in A$ is linked to a node $j\in B$ if and only if ...

**7**

votes

**1**answer

356 views

### Paths in groups

Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.
Question: For what groups does there exist a Hamiltonian ...

**1**

vote

**1**answer

128 views

### Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties.
Actually my question is ...

**0**

votes

**0**answers

92 views

### Has this type of Cayley graphs been studied before?

Let $\mathbb F_q $ be a finite field of characteristic 2.
Let $ x^2 + Sx +P \in \mathbb F_q[x] $ be an irreducible polynomial over $ \mathbb F_q $.
Let $$ T = \{ \left( \begin{matrix}
...

**17**

votes

**0**answers

156 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**4**

votes

**3**answers

147 views

### Is there any partition of a regular graph which in any part there exists a vertex with all its neighborhood?

Let we have a regular graph. I want to know if we can partition the vertex set of this graph while in any part there exist a vertex with all its neighborhood?