Tagged Questions

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

learn more… | top users | synonyms

6
votes
2answers
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
1answer
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
2answers
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
4answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
3answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
6answers
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
1answer
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
2answers
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
0answers
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
1answer
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
2answers
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
1answer
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
5answers
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
0answers
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
0answers
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
0answers
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
3answers
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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?