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

-1
votes
0answers
6 views

Can Singular Value Decomposition Optimal Newman Modularity?

I face some problem on the way home. I want to optimize Newman Modularity Q , Can I use SVD to do that? Thanks!
-4
votes
0answers
46 views

how should one locate ambulance stations so as to best serve the needs of the community..tnx [on hold]

how should one locate ambulance stations so as to best serve the needs of the community i don't know what algorithm to use, any suggestion/s?
4
votes
0answers
40 views

Connection between connectivity and cohesion of a graph

Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path. A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...
-3
votes
0answers
43 views

Graph Theory - k-connected graph [on hold]

I am trying to understand the concept of k-connected graphs in graph thoery. Reference books state that a graph G is k-connected if G is connected and if its vertex connectivity is greater than or ...
1
vote
1answer
42 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...
1
vote
0answers
49 views

Probabilistic proof for expander existence [on hold]

I am new to probabilistic proofs and trying to understand them better. Apparently, a common probabilistic proof focuses on the existence of expanders (eg. vertex expanders). I've been using the search ...
18
votes
2answers
1k views

An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem: Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
0
votes
0answers
158 views

Limit Group decomposition

I would need a clarification about a statement in the article Limit groups and groups acting freely on $\mathbb{R}^n$-trees by Vincent Guirardel. First recall that a limit group is a finitely ...
-4
votes
0answers
63 views

Graph theory and topology [on hold]

I have related topological ideals with vertex magic totallabeling in graph theory. Is there any possibility to relate vertex magic totallabeling with generalized topology in a very interesting way? ...
3
votes
1answer
82 views

Create matrix containing values in [0,1] where sum of all diagonals and anti-diagonals is fixed

The problem I am facing sounds at first glance pretty simple. However, as very often, it seems more complicated than I first assumed: I want to calculate a matrix $P = (p_{j,k}) \in \mathbb{R}^{n ...
4
votes
0answers
86 views

A digraph related to permutations

A finite sequence of distinct real numbers of length $n$ determines a linear order of $\{1,\ldots,n\}$, by mapping position to rank; call this the permutation of the sequence. Consider the following ...
3
votes
0answers
82 views

What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
2
votes
0answers
54 views

Edge-disjoint path-systems in infinite digraphs

Let $ D=(V,A) $ be a directed graph without backward-infinite paths and let $ \{ s_i \}_{i<\lambda},U \subset V $ where $ \lambda $ is some cardinal. Assume that for all $ u\in U $ there is a ...
1
vote
0answers
35 views

Mappings between adaptive networks and Markov processes

Are there any known mappings between adaptive networks models (i.e. graph model representations of networks where the internal vertex dynamics and connectivity topology can change subject to specific ...
-1
votes
0answers
46 views

Looking for an example of a contour integral with matrix entries [closed]

Let $A$ be a matrix (if needed assume it to be the adjacency matrix of graph). Let one be given two functions $P(z)$ and $Q(z,A)$ such that both are polynomials in $z$ and $A$, where $z$ is some ...
4
votes
2answers
135 views

How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have. For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...
7
votes
1answer
112 views

Is there a Degenerate Dependency Local Lemma?

The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded. Here I ask whether another possible generalization (for which I could not yet ...
24
votes
0answers
500 views
+250

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...
3
votes
2answers
131 views

The Hadwiger number of $L(K_n)$

For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the line graph $L(K_n)$ of the complete graph $K_n$ as follows: $V(L(K_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b ...
1
vote
1answer
113 views

Implication between Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture?

The Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture can be stated in a very similar form: Erdös-Faber-Lovasz conjecture: for all finite simple undirected graphs $G=(V,E)$ we have $\chi(G)\leq ...
9
votes
3answers
659 views

Is every graph an edge-crossing graph?

Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph ...
4
votes
4answers
269 views

Request for examples of 4-regular, non-planar, girth at least 5 graphs

Edit: As David Eppstein points out (in his answer below) the assumption that the graph is non-planar is redundant. Thank you to everyone who answered/commented. I have a problem about geometric ...
2
votes
1answer
38 views

Adding vertex-disjoint edges to reduce the diameter

Let $G=(V,E)$ be a finited connected graph, $V\neq \emptyset$. Let $[V]^2 := \big\{ \{v,w\}: v, w \in V\text{ and } v\neq w\big\}$. Given $F\subseteq [V]^2$ we say that $F$ is a vertex-disjoint ...
1
vote
0answers
9 views

Is it true that centrality measures in SNA are indicative for most important vertices only?

I read about the limitations of centrality measures on Wikipedia. It says that centrality measures are good only for identifying top most important nodes in a social network. Their relative values can ...
1
vote
1answer
114 views

Is the number of vertices bounded for fixed max degree and fixed diameter?

Are there positive integers $\Delta, d$ such that the following statement is true? For every $n\in \mathbb{N}$ there is a graph $G = (V,E)$ such that $|V| = n$, $\Delta(G) \leq \Delta$ ...
3
votes
1answer
91 views

Diameter of sum-graph over a meager set

We say that $S\subseteq \mathbb{N}$ is meager if $$\text{lim sup}\frac{S\cap\{1,\ldots, n\}}{n} = 0.$$ Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where ...
1
vote
1answer
33 views

Connected components of a sum-graph over an infinite set

Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where $$E = \big\{\{m,n\}: m,n \in \mathbb{N} \text{ and } m+n\in S\big\}.$$ Is there an infinite subset ...
0
votes
1answer
60 views

Edge-disjoint cycles in graphs

Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edge-disjoint cycles of length $k$ in $G$? If not is there a proof that this ...
6
votes
1answer
111 views

Diameter of sum-graph over a non-meager set

Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where $$E = \big\{\{m,n\}: m,n \in \mathbb{N} \text{ and } m+n\in S\big\}.$$ We say that $S\subseteq ...
0
votes
1answer
39 views

Sum-graph over an infinite set

Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where $$E = \big\{\{m,n\}: m,n \in \mathbb{N} \text{ and } m+n\in S\big\}.$$ If $S$ is infinite, is $G_S$ ...
0
votes
0answers
40 views

Quasi-transitive decomposition of a transitive graph

Let $G=(V,E)$ be a simple digraph that is semi-complete (ie. there's at least one arc between each unordered pair of vertices) and quasi-transitive (ie. its complement is transitive). Is it true that ...
1
vote
0answers
52 views

What's the complexity of the one sink directed subgraph isomorphism problem?

I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to ...
10
votes
3answers
347 views

The diameter of a certain graph on the positive integers

Let $G(n)$ be the graph whose vertices are the positive integers $1,2,3,4, \ldots, n$ two of which are joined by an edge if their sum is a square. Is the diameter of this graph 4 for all sufficiently ...
2
votes
0answers
37 views

Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?

What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?
3
votes
1answer
64 views

Dense high-degree sub-graphs of dense graphs

Let $G$ be a graph with $n$ vertices and $m$ edges, and let $d=\lfloor\frac{m}{n}\rfloor$ be the rounded-down average-degree. A lemma that is attributed to Erdos says that $G$ has a non-empty induced ...
3
votes
1answer
102 views

Infinite non-splittable graphs

Let $G=(V,E)$ be a graph. For $v\in V$ we set $N(v)=\{w\in V:\{v,w\}\in E\}$. We say that $G$ is splittable if there are $S,T\subseteq V$ with $S\cap T=\emptyset$ and $S\cup T = V$ such that for all ...
1
vote
2answers
122 views

A certain matrix associated to graphs

I am not very familiar with graph theory, but I need some results for my work. Thus, the question is, whether the following has already been studied and where I can find it. Let $G=(V,E)$ be an graph ...
5
votes
0answers
244 views

Have topographs been studied before?

This is my first post on MO so I hope this question is suitable. I have quite a few definitions which I will need to state before my questions at the end of this post. Please let me know if anything ...
-2
votes
1answer
108 views

About structure of the set of perfect matchings of $K_{n,n}$

Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure ...
8
votes
0answers
151 views

Lovasz's Path removal conjecture

The Lovász Path Removal Conjecture states: For any positive integer $k$, there exists a minimum positive integer $f(k)$ such that, for any two vertices $x$, $y$ in any $f(k)$-vertex-connected ...
7
votes
0answers
266 views

Does this inequality always hold?

Denote the adjacency matrix of a given undirected graph by $g$. It is an $n$-by-$n$ symmetric Boolean matrix with elements on the diagonal to be zero ($n\geq 3$). Let $g_{12}=g_{21}=g_{13}=g_{31}=1$ ...
6
votes
1answer
175 views

Isometries of some simple Cayley graphs

Consider a Cayley graph of a group $G$ with respect to a symmetric finite generating set $S$. There are some obvious candidates to isometries of this graph - for example, translation by elements of ...
2
votes
1answer
66 views

Are there non-isomorphic graphs with rationally orthogonal similar adjacency matrices?

Let $A_G,A_H$ be the adjacency matrices of two non-isomorphic graphs. Let $P$ be orthogonal matrix with rational entries. Is it possible $A_G = P^{-1}A_H P$? Paper gives algorithm for ...
5
votes
2answers
256 views

When are the adjacency matrices of non-isomorphic graphs similar?

From Wikipedia. In linear algebra, two n-by-n matrices A and B are called similar if $$ B = P^{-1} A P$$ for some invertible n-by-n matrix $P$. If $P$ is a permutation matrix, $A$ and $B$ are ...
1
vote
1answer
62 views

Connection between Barnette conjecture and hardness of cubic graph decomposition

Motivated by this post on cubic graphs decompositions and the connection to Barnette conjecture, I am interested in decomposing a connected bridgeless cubic graph into edge-disjoint paths of length 3 ...
1
vote
1answer
86 views

About the upper bound on the roots of the matching polynomial

Heilman and Lieb had proven that if a graph had $d$ as its maximum vertex degree then the roots of the matching polynomial are bounded from above by $2\sqrt{d-1}$. Is there a modern exposition of ...
1
vote
2answers
115 views

Nauty software package and weighted graphs

I am working with software package Nauty. It there a way to add weighted graphs in nauty software package?
3
votes
1answer
158 views

About the second largest adjacency eigenvalue of Abelian Cayley graphs

[Assume all groups are finite] One knows the general statement that the sum of the values of the character function on the generating set is an eigenvalue of a Cayley graph. But the above doesn't ...
0
votes
1answer
49 views

Maximum degree and matching number

Let $G=(V,E)$ be a finite graph. We write $\nu(G)$ for the matching number of $G$. Is there $\varepsilon > 0$ such that we have $$\frac{\nu(G)+\Delta(G)}{V(G)} \geq \varepsilon$$ for all finite ...
5
votes
0answers
117 views

$\kappa$-impediments (according to Shelah, Nash-Williams, Aharoni)

Let $\Gamma = (M, W, K)$ be a bipartite graph, that is $M, W$ are sets and $K\subseteq M\times W$. If there is an injective function $f:M\to W$ such that $f\subseteq K$ we say $f$ is an espousal and ...