**7**

votes

**1**answer

508 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**1**

vote

**0**answers

20 views

### Partitioning the vertex set of a planar bipartite graph into a tree and an independent set

Let $G = (V, E)$ be a planar bipartite graph such that there is a partition $(V1, V2)$ of $V$ where $V1$ induces a tree and $V2$ induces an independent set.
Is there a characterization of such ...

**-4**

votes

**0**answers

39 views

### Self avoiding walk problem? [on hold]

As in the image we can see that there are black spots and moving from spot to another is 1 move.
Can we create a function which will tell us the position after say 119 moves, 143 moves etc without ...

**0**

votes

**1**answer

234 views

### Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...

**7**

votes

**1**answer

119 views

### Equalizing Geometric means of Graph Cycles

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...

**1**

vote

**0**answers

99 views

+50

### A path optimisation problem

Consider a graph of $n$ nodes randomly located in $[0,1]^2$. Each node moves following a path randomly chosen from the set of all possible paths. Regard nodes as attackers. A policeman seeks an ...

**0**

votes

**1**answer

46 views

### Maximal chromatic number with a fixed number of edges

Given a graph $G$ with $m$ edges, what is the maximum chromatic number $\chi(G)$ that the graph can have?
My guess is that $\chi(G) \leq r(m)$ where $r(m) := \max\{k\in \mathbb{N}:
\frac{k(k-1)}{2} ...

**6**

votes

**1**answer

140 views

### Eigenvalue inequality for regular graphs

I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim ...

**7**

votes

**4**answers

949 views

### Prime numbers $p$ not of the form $ab + bc + ac$ $(0 < a < b < c )$ (and related questions)

If we ask which natural numbers n are not expressible as $n = ab + bc + ca$ ($0 < a < b < c$) then this is a well known open problem. Numbers not expressible in such form are called ...

**3**

votes

**3**answers

3k views

### What is a good algorithm to measure similarity between two dynamic graphs?

I am using graphs to represent structure present in a scene. The vertices represent the objects in the scene and the edges represent the relationship between two nodes(touching, overlapping, none). ...

**1**

vote

**1**answer

108 views

### Sum of Eigenvectors Entries of an Adjacency Matrix

I have a question regarding the sums $\sum_{i=1}^{n}v_{j}\left(i\right)$ where $v_j$ are eigenvectors of adjacency matrix $A$ which have been normalized to unit length.
Ordering the eigenvectors by ...

**3**

votes

**1**answer

257 views

### inequality with exponents

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v ...

**-1**

votes

**2**answers

91 views

### Do graphs with $\omega(G) = \chi(G)$ grow “common” as $|V|$ grows large?

On the set $[n]:= \{1,\ldots,n\}$ we consider the set $${\cal P}_2([n]) = \big\{\{a,b\}: a,b \in [n], a\neq b\big\}.$$
Since $$|{\cal P}_2([n])| =2^{n \choose 2}$$ there are exactly $2^{n\choose 2}$ ...

**3**

votes

**1**answer

104 views

### Algorithm to count the number of perfect matchings in non planar graph

I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...

**2**

votes

**2**answers

160 views

### SVD vs Fourier analysis for data.

Fourier analysis is useful for analysis in the frequency domain. SVD on the other hand is useful for analysis of data, and expressing noise in the data. I have a problem that needs extensive data ...

**1**

vote

**0**answers

39 views

### Eigenvalues of the sum of Laplacian matrix and the all ones matrix [migrated]

Given an undirected graph and its Laplacian is $L$.
I need to find the eigenvalues of the sum: $L + \mathbf{11^T}$ (where $\mathbf{1}$ is the all-ones vector, which means that $\mathbf{11^T}$ is a ...

**2**

votes

**3**answers

745 views

### A conjectured criterion for 4-colorable graphs

I tried to find a solution to this in the web but couldn't.
Can you tell me if the following sentence is correct or else give me a counterexample?
$G$ is $4$-colorable if and only if each sub-graph ...

**0**

votes

**0**answers

27 views

### Arc-transitive graphs of prime valency with non-solvable automorphism group

Let $\Gamma$ be a $G$-arc-transitive graph of prime valency and $G$ be non-solvable. Is there any classification of such graph?

**2**

votes

**1**answer

38 views

### Edge-perspective degree distribution

I was reading this paper when I came across something called the edge-perspective degree distribution in a network. Consider a graph $G$, the degree distribution of whose nodes is $f(d)$. They say the ...

**11**

votes

**1**answer

141 views

### Graphs with a coloring that majorizes all other colorings

By a coloring of a graph $G = (V,E)$ I mean a map $\kappa:V\to\mathbb{N}$ such that $\kappa(u)\ne \kappa(v)$ whenever $u$ and $v$ are adjacent. (Sometimes this is called a proper coloring but I am ...

**11**

votes

**1**answer

245 views

### Pursuit-Evasion type game on graph (“Flyswatter game”)

An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...

**1**

vote

**2**answers

66 views

### Position likelihood in a 2D graph [closed]

I am looking for general principles or specific answers to this generic example.
Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some ...

**0**

votes

**0**answers

102 views

### Is there any result on the homomorphic images of hypercube graphs?

Let $Q_n$ be a hypercube graph and $\phi: Q_n\to G$ a surjective simplicial graph morphism i.e. if $u,v$ are adjacent vertices in $Q_n$ then either $\phi(u)=\phi(v)$ or $\phi(u),\phi(v)$ are adjacent. ...

**0**

votes

**0**answers

51 views

### Polynomial time approximation schemes

The relationship between the minimum vertex cover and maximum independent set is a well established one. I was wondering if
If for some class of graphs $\mathcal{S}$ there exists a PTAS or even an ...

**0**

votes

**1**answer

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

**2**

votes

**2**answers

149 views

### Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...

**1**

vote

**1**answer

48 views

### Properties of very well covered graph

Definition: Very well covered graph to be a well-covered graph (possibly disconnected, but with no isolated vertices) in which each
maximal independent set (and therefore also each minimal ...

**33**

votes

**2**answers

2k views

### What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this ...

**-1**

votes

**0**answers

76 views

### What the number of the components of a specific subgraph? [closed]

Given a n vertices graph $G$, take two edge-disjoint matchings in $G$, namely $M_{1}$ and $M_{2}$, such that they cover $n-\alpha$ vertices each. In our case, $\alpha$ can be a constant or a function ...

**1**

vote

**1**answer

117 views

### Uniquely describing a graph

According to answers here http://math.stackexchange.com/questions/1524598/a-general-incidence-problem// an unigraph comes from unigraphic degree sequences if it can be uniquely determined by its ...

**3**

votes

**1**answer

74 views

### Is there any vertex-transitive non-Cayley graph with 24 vertices and valency 5?

I know that, by D. McKay and C. E. Praeger papers" Vertex-transitive graphs which are not Cayley graphs I", there exist 112 non-Cayley vertex-transitive graph with 24 vertices.
Is there any such ...

**2**

votes

**1**answer

98 views

### VLSI circuit embeddings

In the following paper by Valiant
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 ...

**0**

votes

**1**answer

56 views

### Weak Erdos graphs

We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdos graph if there are $n$ subsets $S_1,\ldots, S_n$ of $V$ such that
$V = \bigcup_{n=1}^n S_n$;
each $S_k$ has $n$ elements for ...

**0**

votes

**1**answer

97 views

### Node-edge coloring of graphs

There must be work on this concept, but I am not finding it through
searches, perhaps using the wrong terminology.
Define a node-edge coloring of a graph ...

**0**

votes

**1**answer

49 views

### The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...

**6**

votes

**1**answer

385 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...

**2**

votes

**4**answers

3k views

### What is the n-th power of the adjacency matrix equal to?

A friend (who works on social networking analysis) asked this over at twitter:
What is the n-th power of the adjacency matrix equal to, in terms of paths, NOT walks?
EDIT: Complimentary question: ...

**2**

votes

**2**answers

70 views

### A question about a specific partition of a graph

Let $G=(V,E)$ be a graph and $V=A\cup B$ satisfying
$(1)A\cap B=\emptyset;$
$(2)|N_G(v)\cap B|\geq |N_G(v)\cap A|,\forall v\in A$ and $|N_G(v)\cap A|\geq |N_G(v)\cap B|,\forall v\in B$.
Let ...

**1**

vote

**2**answers

49 views

### Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...

**14**

votes

**1**answer

970 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...

**0**

votes

**0**answers

77 views

### Does anyone know any applications of CW-complexes in graph theory?

As everyone knows :P, a graph is a CW-complex of dimension 1. Knowing that, are there any interesting results in graph theory that arise from working with CW-complexes? And more specifically, in ...

**6**

votes

**2**answers

143 views

### Isomorphic Hadwiger graphs

Let $G$ be a graph, then we define its Hadwiger graph $\textrm{Hadw}(G)$ in the following way:
$V(\textrm{Hadw}(G)) = \{S\subseteq (V(G): S\neq \emptyset\textrm{ and } S \textrm{ is connected}\}$;
...

**-1**

votes

**0**answers

81 views

### $(r+1)$ Clique of a Induced Subgraph ensured by Edge Number of the Graph

$G$ is a $s$ regular graph.
$E$ is the number of edges of $G$.
$n$ is the total number of vertices of $G$.
$A$ is a set of $t$ vertices where $|A| = t;0<t<n$ and $A \subseteq G$.
Problem: ...

**1**

vote

**1**answer

323 views

### Modern books about orders and algebras on trees [closed]

Please help to find books about orders and algebras on trees.
If there is no modern books, please advice good old ones!
I'm more interested in finite trees (my current problem), but infinite ones are ...

**10**

votes

**5**answers

1k views

### Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...

**11**

votes

**1**answer

266 views

### Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?

This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route ...

**8**

votes

**1**answer

155 views

### Expansion in strongly regular graphs

Have you seen the following statement proven anywhere?
Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...

**2**

votes

**3**answers

199 views

### Making integer multisets graphic

Let $M=(X,f)$ be a multiset, where $X$ is the underlying set of elements and $f:X\rightarrow\mathbb{N}$ is the multiplicity function. For every $k\in\mathbb{N}$ put $k\cdot M:=(X,k\cdot f)$. It is ...

**1**

vote

**1**answer

108 views

### Two types of random walkers on square lattice

Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index ...

**1**

vote

**3**answers

143 views

### Minimum number of unlabeled planar graphs

Does anybody know if there is any research on a lower bound on the number of (non-isomorphic) unlabeled planar graphs with maximum node degree $d$?
Alternatively, a lower bound on the number of all ...