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

0
votes
1answer
38 views

Are these three different notions of a graph Laplacian?

I seem to see three different things that are being called the Laplacian of a graph, One is the matrix $L_1 = D - A$ where $D$ is a diagonal matrix consisting of degrees of all the vertices and $A$ ...
0
votes
0answers
17 views

Max flow with minimal requirements algo problem

While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem. The algorithm states: For graph G create an edge from target to ...
0
votes
0answers
23 views

is a network a sum of its subnetworks?

I was wondering if networks/graphs are the sum of their parts. Let's say you have a 15-node network. The spectral density of that network has X kurtosis and Y skewness. You also have a 20-node ...
1
vote
1answer
65 views

n-cube connectivity problem

Given $n\geq 2$, let us consider the n-cube $H_n=(V,E)$, i.e. vertex set $V$ is $\{0,1\}^n$. Here, the edges of $H_n$ are directed, oriented by set inclusion, i.e., $(x,y)\in E$ iff $x\subseteq y$ and ...
6
votes
2answers
104 views

Realizing a monoid as $\mathrm{End}(G)$ for some graph $G$

This question relates to Realizing groups as automorphism groups of graphs. Given a monoid $M$, is there a graph $G$ such that the endomorphism monoid $\textrm{End}(G)$ is isomorphic to $M$?
-1
votes
0answers
38 views

Random Spanning Tree Edge Probability [on hold]

I am working on a problem with a Loop Erased Random Walk used to create random spanning trees. The problem has many parts, but there are two hints to help with the more complicated problems Figure ...
-1
votes
0answers
74 views

Are there any special properties of graph eigenvalues of perfect matchings? [on hold]

On a given set of vertices say one has added edges such that either of the conditions hold, (1) That the edges are such that they can be decomposed into $k$ (edge)disjoint perfect matchings. (2) ...
-2
votes
0answers
82 views

What is the characterization of a graph Laplacian? [on hold]

Given a matrix, what properties must it have so that its ensured that there exists a graph whose Laplacian it would be? (...may be you can consider weighted and unweighted cases separately...) And ...
8
votes
1answer
279 views

Could there be an exact formula for the Ramsey numbers?

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$. Is it possible that there ...
3
votes
1answer
76 views

Strongly asymmetric graphs

Asymmetric graphs are graphs that have a trivial automorphism group $\textrm{Aut}(G)$, i.e. the only graph isomorphism from $G$ to itself is the identity. Let's call a graph $G$ strongly asymmetric ...
0
votes
0answers
61 views

Number of graphs with M edges that does not contain K-clique [on hold]

If we consider the space of graphs $G(n,M)$ where $M$ denotes the number of edges. Is there any known way of calculating the number of graphs within this space that does not contain any k-cliques? Can ...
5
votes
1answer
80 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}\}$; ...
2
votes
1answer
180 views

Counting Ribbon graphs

Let $G$ be a ribbon graph (sometimes called fat graph) with $v$ vertices and $e$ edges. Furthermore each vertex is of degree $d$. Q) What is the number of $G$ with the above properties? I mean does ...
2
votes
0answers
41 views

relationship of max-sat and min-cut in theory and practice

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model: For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...
0
votes
1answer
76 views

Finding nodes with a particular weight in a graph

Say that an edge $e$ is incident to a node $v$ if one of its two extremes is $v$. Then we can also say that $v$ is hit by $e$. We might define the notion of "weight of a node $v$" as the sum of all ...
3
votes
1answer
151 views

Determinant of the oriented adjacency matrix of a tree

Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries $$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\ -1 ...
2
votes
3answers
540 views

Koebe–Andreev–Thurston theorem - where can I find a proof?

Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
1
vote
0answers
37 views

Solutions for n such that the path number to the n-th node is also n in a complete, rooted, ordered k-ary tree

The path to find the $n$-th node within a complete, rooted, ordered $k$-ary tree can be represented by a number to the base $(k+1)$ that contains no zero digits. See A245905 in OEIS as an example for ...
5
votes
1answer
128 views

Number of median graphs?

What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...
-2
votes
1answer
77 views

how to reduce 3-colorable graph to this? [closed]

suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to ...
0
votes
0answers
11 views

matching Robinson-Foulds distance and way to compute RF dist in Phylip

In Comparison of Phylogenetic Trees, Robinson D.F. and Foulds L.R., didn't show how to compute the RF distance between trees, counting the different partition generated by the removing of an internal ...
-2
votes
0answers
43 views

when a given graph is 3-colorable? [closed]

I want to use graph 3-colorability to prove a problem is NP-complete But I'm not sure when a given graph is 3-colorable. I think if it doesn't have any node to be connected to all 3 vertices of a ...
-4
votes
0answers
65 views

About diagonal entries of the graph Laplacian [on hold]

[..in the following you can assume its a regular graph if necessary..] Is anything special known about them? Are they characterized in any other way? Is the largest diagonal entry in any power of ...
0
votes
0answers
76 views

independent subset problems [closed]

I'm interested in the following which i suspect is probably a well studied problem. Given a set $N=\{1,2,...,n\}$ and $M=\{1,2,...,m\}$ consider a map $$f:N\rightarrow 2^{M}$$ (elements of $N$ to ...
1
vote
1answer
65 views

What is “graph-directed iterated function”?

Im translating an article about Rauzy fractal and I ran into this sentence: ...
9
votes
2answers
382 views

Can a parent and child node have the same type in a well-founded digraph tree?

$\newcommand\toward{\rightharpoonup}$It would help me to understand something in a current research project if someone could provide an example of directed graph $\langle G,\toward\rangle$ with the ...
7
votes
4answers
208 views

4-regular graph with every edge lying in a unique 4-cycle

What are all 4-regular graphs such that every edge in the graph lies in a unique-4 cycle? Among all such graphs, if we impose a further restriction that any two 4-cycles in the graph have at most one ...
0
votes
1answer
30 views

Petersen 2-factor decomposition theorem for directed graphs

Petersen proved that every 2k-regular graph can be decomposed into k disjoint 2-factors. I would like to know that is it true that if G is a directed regular graph (d_out(v)=d_in(v)=k), then can G be ...
1
vote
1answer
105 views

NP hard problems on UD graphs

I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard. ...
2
votes
1answer
133 views

Graph automorphism that swaps two pairs of nodes

Suppose we have two automorphisms on a graph $G$ such that each one swaps a separate pairs of vertices. Is it possible to construct (or prove the existence of) a third automorphism that swaps both ...
0
votes
1answer
54 views

Intersection graphs

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?
0
votes
0answers
81 views

Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements: (H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$. ...
2
votes
1answer
84 views

irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...
12
votes
0answers
168 views

Coloring the edges of a torus graph

Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most ...
8
votes
1answer
179 views

Vertex-primitive graphs with two vertices having almost the same neighbourhood

Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$ Question: Is it true that $\Gamma$ must either be a complete graph or have ...
0
votes
0answers
48 views

Expected number of distinct nodes visited in a directed bipartite graph [migrated]

Let $G = (V,E)$ be a directed bipartite graph with $V = \{I \cup O\}$ where $\left\vert{I}\right\vert = n$ and $\left\vert{O}\right\vert = m$. All the edges start from a vertex in $I$ and end on a ...
0
votes
1answer
31 views

Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ ...
0
votes
1answer
90 views

How to solve the opposite of max flow problem? [closed]

Each edge in graph has a minimum bound instead of a maximum capacity. The goal is to find the minimum flow such that every edge in graph has flow larger than it's lower bound. I tried to use Ford ...
7
votes
3answers
346 views

Is there a continuous analogue of Ramanujan graphs?

I think it might help to think of the following definition of a Ramanujan graph - a graph whose non-trivial eigenvalues are such that their magnitude is bounded above by the spectral radius of its ...
4
votes
0answers
107 views

minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
6
votes
2answers
224 views

Counting valid coordinates

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in ...
2
votes
2answers
49 views

Deciding whether a given graph has an f-factor or not!

Given a graph $G$ with $n$ vertices and a function $f$ from $\{1,2,...,n\}$ to non-negative integers, Does there exist an efficient (for example polynomial time) algorithm, that decides whether $G$ ...
1
vote
1answer
136 views

Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let $p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$. I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...
0
votes
1answer
70 views

Using upper bound information in graph search

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex. In other ...
2
votes
2answers
79 views

About the roots of the matching polynomial

Can someone kindly give me an expository reference on matching polynomial and its roots? (there is a proof that they are always real?) I saw these two related discussions, Roots of matching ...
2
votes
0answers
60 views

Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?

Terry Tao's notes on expander graphs has the following exercise: Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and ...
1
vote
1answer
206 views

Probability of connected graph on torus

Let $G = (V, E)$ be a graph on n vertices constructed in the following way: Each vertex $v \in V$ is positioned uniform randomly in $[0, 1] × [0, 1]$. Connect two vertices $u, v \in V$ if $d(v,u) ≤ ...
2
votes
0answers
53 views

Fixing (non)-independency of a the subfamilies of finitely many events.

I'm would be interesting in any construction of a probability space with n events (n is given), where for every subset of these events, it is also given whether or not, the family is mutually ...
1
vote
0answers
48 views

clustering in a graph on boolean functions

Fix some n and k. Consider the following directed graph: vertices are all functions $2^n\rightarrow 2^n$ and a vertex f has an edge to a vertex g for every h such that $f=h\circ g$ and h depends only ...
2
votes
2answers
205 views

Find all faces in a graph from list of edges

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...