**3**

votes

**2**answers

152 views

### Distance between two networks

Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) ...

**0**

votes

**0**answers

20 views

### Complexity of graph isomorphism in $(P_4 \cup K_1,\overline{3K_2})$-free graphs

Related to this question where isomorphism preserving
transformation maps triangle-free graphs to $(P_4 \cup K_1,\overline{3K_2})$-free graphs.
What is the complexity of graph isomorphism in $(P_4 ...

**3**

votes

**1**answer

75 views

### Graph transformation related to graph isomorphism

Basically got graph transformation related to graph
isomorphism.
Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$.
...

**3**

votes

**1**answer

159 views

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

**9**

votes

**1**answer

377 views

### Existence of a sink in directed graphs with a certain structure

I'm not a mathematician (I'm an economist) but I hope that this problem is sufficiently non-trivial that someone here will find it interesting.
Motivation:
I'm trying to model how workers decide ...

**0**

votes

**1**answer

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

**0**

votes

**0**answers

21 views

### Solving Least square problem in Matlab using fmincon [on hold]

I am trying to find an optimal solution for the following least square problem
\begin{equation}
\min_{w} \sum_{j}^{}\sum_{i}^{} \left( \hat{T}_j(t_i) - T(t_i, w) \right)^2
\end{equation}
where ...

**3**

votes

**3**answers

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

**4**

votes

**1**answer

418 views

### Surprising connection between linear algebra and graph theory

What is the intuition for linear algebra being such an effective tool to resolve questions regarding graphs?
For example, one can determine if a given graph is connected by computing its Laplacian ...

**0**

votes

**0**answers

18 views

### Splitting lemma for digraph and preserving local rooted-edge connectivity?

Let $G$ be a directed graph. $\lambda(x,y,G)$ is the maximum number of edge disjoint paths from $x$ to $y$ in $G$
The local $r$-rooted connectivity of $x$ in $G$ is $\lambda(r,x,G)$.
The global ...

**2**

votes

**1**answer

112 views

### Minimum length path touching $n$ circles

Given $n$ non-overlapping circles of radius $1$ (i.e., the distance between the centers of any two circles is greater than $2$), how to find the minimum length path (the path can be of any form) that ...

**2**

votes

**1**answer

76 views

### triangles in a graph with specified clique number

Turan's theorem tells us that if m is the number of edges in a graph with n vertices and clique number r, then 2m <= (r - 1)n^2/r.
If t denotes the number of triangles, is there a similar ...

**3**

votes

**2**answers

320 views

### An upper bound for number of triangles in a graph

A small inquiry about something that has been troubling me for the whole afternoon without luck: is there any known result about say simple graphs $G(V,E)$ with some property $\mathcal{P}$ such that ...

**3**

votes

**0**answers

37 views

### Algorithm to construct metric space endomorphism with controlled square

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be ...

**5**

votes

**3**answers

384 views

### Relationship between triangle free graphs and their minimum degree

Let $T$ be a triangle-free graph on $n$ vertices with minimum degree $\delta$ (which can be $0$). How does one show that $n >2\delta -1$? It seems to be true for bipartite graphs, but I cannot see ...

**5**

votes

**1**answer

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

**2**

votes

**1**answer

82 views

### About the diameter of a graph after removing orientation

This question was posted a few days ago on the Mathematics StackExchange, but so far it has not been answered. Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we ...

**0**

votes

**1**answer

45 views

### N random walkers that hit node v in a graph

Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...

**2**

votes

**1**answer

148 views

### Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let ...

**0**

votes

**1**answer

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

**4**

votes

**0**answers

29 views

### What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial
is a bivariate polynomial with positive integer coefficient which is a graph
invariant and can be defined recursively.
Evaluating it is $\#P$-complete even when restricted to ...

**1**

vote

**2**answers

161 views

### Strongly connected DAG from any connected undirected graph?

I have the following question. It seems likely to be true - can anyone provide a standard reference?
Given:
A connected, undirected graph.
Question 1:
Can we assume a single direction for each edge ...

**10**

votes

**0**answers

194 views

### Mixing properties of random walks on graphs [migrated]

I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs.
One of the main ideas of the paper is that random walks on graphs can be used to find sets with small ...

**0**

votes

**4**answers

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

**6**

votes

**0**answers

79 views

### Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...

**32**

votes

**6**answers

2k 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 ...

**3**

votes

**0**answers

80 views

### Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large.
An agent can move in the area at ...

**6**

votes

**2**answers

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

**0**

votes

**0**answers

89 views

### Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$

Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix ...

**4**

votes

**2**answers

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

**4**

votes

**1**answer

109 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

**1**answer

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

**21**

votes

**7**answers

3k views

### Spectral graph theory: Interpretability of eigenvalues and -vectors

I thought "Wow!" when I learned that the eigenvector of the adjacency matrix of a cycle graph $C_n$ corresponding to the second largest eigenvalue gives the coordinates of the vertices when equally ...

**0**

votes

**2**answers

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

**2**

votes

**1**answer

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

**4**

votes

**1**answer

97 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, ...

**3**

votes

**1**answer

97 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

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

**16**

votes

**1**answer

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

**4**

votes

**1**answer

200 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 ≥ ...

**8**

votes

**3**answers

774 views

### Classification of degree (bi-)sequences of bipartite graphs?

It is known that the sequence $d_1 \geq d_2 \geq \ldots \geq d_n$ of nonnegative integers is the degree sequence of a graph if and only if the sum of the $d_i$ is even and we have
\[
\sum_{i = 1}^k ...

**0**

votes

**0**answers

39 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

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

**6**

votes

**2**answers

192 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 = ...

**0**

votes

**0**answers

38 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

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

**0**

votes

**1**answer

139 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) ...

**-4**

votes

**1**answer

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

**10**

votes

**1**answer

563 views

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

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

**7**

votes

**2**answers

325 views

### Graphs with many edges avoided by Hamiltonian cycles

Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...