**0**

votes

**0**answers

14 views

### Algorithm: In every vertex whose distance from $v_i$ is not greater that $d_i$ place $r_i$ objects

You are given a tree with $N$ $(1 \le N \le 10^5)$ vertices and $N - 1$ edges. Weight of edge won't exceed 200. Design an algorithm to do $Q$ $(1 \le Q \le 10^5)$ operations of two types as fast as ...

**1**

vote

**1**answer

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

**5**

votes

**0**answers

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

**0**

votes

**0**answers

34 views

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

**3**

votes

**1**answer

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

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

**0**

votes

**0**answers

25 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?

**-1**

votes

**2**answers

88 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}$ ...

**2**

votes

**1**answer

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

**0**

votes

**0**answers

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

**1**

vote

**1**answer

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

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

**0**

votes

**0**answers

44 views

### Tripartite Graph Algorithm [closed]

Is there an algorithm for determining whether or not a graph is tripartite? I know about the algorithm for determining whether or not a graph is bipartite, and was wondering if there is something ...

**-2**

votes

**0**answers

26 views

### Testing connectivity after a node is removed [closed]

What is the best way to test that a network is still connected after a node has been removed? I am using Matlab.

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

**0**

votes

**1**answer

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

**11**

votes

**1**answer

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

**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**

vote

**1**answer

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

**2**

votes

**2**answers

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

**11**

votes

**1**answer

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

**0**

votes

**0**answers

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

**0**

votes

**1**answer

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

**-1**

votes

**0**answers

79 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: ...

**3**

votes

**1**answer

72 views

### Probabilistic many-to-one matching

Let $p<1$ be a constant. Consider two sets $A,B$ with $n$ and $nf(n)$ vertices, respectively, where $f(n)$ is an integer. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears ...

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

**2**

votes

**2**answers

107 views

### Matching with probabilistic edges

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...

**3**

votes

**1**answer

126 views

### Volume of the convex hull of the set of all graphic sequences of a given length

Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let
$$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ ...

**1**

vote

**1**answer

88 views

### Eulerian graphs with prescribed number of edges

Under what conditions there exists an $n$-vertex eulerian graph with $m$ edges for $1\leq m\leq\frac{n(n-1)}{2}$?

**8**

votes

**1**answer

154 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$ ...

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

**1**

vote

**1**answer

52 views

### Duality and Euler paths in graphs

I'm computer scientist and in one of my researches I'm facing this question:
if I have a planar graph that admits an Euler path (i.e. has 0 or 2 odd degree vertices, as Euler's theorem says), then his ...

**9**

votes

**3**answers

247 views

### Labeling edges of an icosahedron with sum constraints

The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that:
Three ...

**1**

vote

**0**answers

19 views

### Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph.
I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...

**3**

votes

**1**answer

95 views

### Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. ...

**0**

votes

**1**answer

30 views

### Number of $k$-walks containing a vertex in an unweighted multigraph

Let $G = (V,E,W)$ be a weighted graph, where each edge $e = (v_i,v_j)$ has weight $w_{ij} \in \mathbb Z^+ \cup \{0\}$. By replacing $e$ with $w_{ij}$ copies of unweighted multiedges, a weighted graph ...

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

**16**

votes

**0**answers

247 views

### Zero curves of Tutte Polynomials?

There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...

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

**4**

votes

**0**answers

66 views

### A relaxation of proper coloring

I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...

**6**

votes

**2**answers

251 views

### extremal bipartite graph

I'm facing the following question:
Given a bipartite graph $G = (L \cup R, E)$.
Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.
What is a minimal possible number ...

**0**

votes

**0**answers

30 views

### Is a nonmonotone symmetric function of eigenvalues of laplacian matrix, a sobmodular set function over the edges of the graph?

Let $L_G\in \mathbb{R}^{n \times n}$ be Laplacian matrix of an undirected connected Graph $G$ and $0=\lambda_1<\lambda_2\leq\dots\leq\lambda_n$ be eigenvalues of $L_G$.
Further, let for a positive ...

**4**

votes

**1**answer

81 views

### $k$-planar graphs and genus

Is there a simple function that connects $k$ in $k$-planar graphs and genus of such graphs?
If there is no simple function is there any non-trivial upper and lower bound?

**3**

votes

**0**answers

67 views

### Group Travel Salesman Problem

For the following Group Traveling Salesman problem, I'd like to know if there exists some poly-time approximation algorithm with constant approximation factor.
Group TSP is defined as follows: Take a ...

**7**

votes

**2**answers

206 views

### A Different 2-factor in a graph

We know that a k-factor of G is a k-regular spanning subgraph of G. And if G is 4-regular (or 2k-regular), it can be partitioned into 2 (k) edge-disjoint 2-factors (Petersen 1891).
My question is in ...

**-1**

votes

**2**answers

71 views

### Is there a formula that determines the size of the leafage of a graph's spanning tree? [closed]

In general terms, all the spanning trees of a graph G have the same number of leaves.
Is there any formula that allows us to know the number of leaves in terms of |V| and |E| for any spanning tree of ...

**0**

votes

**2**answers

95 views

### Infinite k-connected planar graphs

By planar I mean there is no $K_{3,3}$ minor of $K_5$ minor. Also, I am only considering the $\mathbb{R}^2$ surface, not a torus not any other surfaces.
I know that to construct such graph, For $k ...

**2**

votes

**1**answer

125 views

### Does this version of Hadwiger's conjecture hold for graphs with infinite chromatic number?

Let $G = (V,E)$ be a finite, simple, undirected graph. Hadwiger's conjecture states that
(Hadw): $K_{\chi(G)}$ is a minor of $G$.
It turns out that for finite graphs, (Hadw) is equivalent to the ...

**2**

votes

**0**answers

51 views

### The numbers of edge colorings and partitions into vertex covers

Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ ...