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

-2
votes
0answers
45 views

What does this graph notation mean? E\S [on hold]

I am studying graph theory right now but I am confused what E\S means where both E and S are sets of edges. What does the "\" indicate?
4
votes
3answers
250 views

Perimeter/Neighborhood of a graph on grid

Hello, I have a $\sqrt{n}\times\sqrt{n}$ lattice graph $G=(V,E)$ i.e. vertices on said 2-dim integer lattice, and two vertices have an edge if their $L_1$ distance is one. Now I want to claim ...
6
votes
1answer
103 views

When is the tensor product of two graphs planar?

Given two graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$, the tensor product of $G$ and $H$ is the graph $G \times H = (V,E)$, where $V=V_1 \times V_2$ is the Cartesian product of the $V_i$ and $ (u,v) \ E \ ...
3
votes
1answer
229 views

Min Bend Orthogonal Knots

I am seeking literature on 3D orthogonal drawings of knots, especially minimum bend drawings. An orthogonal drawing employs segments parallel to the axes of a Cartesian coordinate system. A bend is a ...
4
votes
1answer
81 views

Hadwiger's conjecture for coloring number instead of chromatic number

For any graph $G=(V,E)$, the coloring number $\text{Col}(G)$ is defined to be the smallest cardinal $\kappa$ such that there is a well-ordering $\leq$ on $V$ such that for every vertex $v\in V$ we ...
0
votes
0answers
33 views

Weighted eigenvector-entry sums of bipartite graphs

Let $\lambda_m$ denote the $m$-th eigenvalue of the adjacency matrix $A$ of a bipartite graph $G$ of order $N$ and ${\bf v}_m$ the normalized eigenvector corresponding to $\lambda_m$. I am looking for ...
3
votes
0answers
27 views

Isomorphic Hadwiger graphs of connected infinite 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
vote
1answer
52 views

Hadwiger-Nelson problem in higher dimensions

Given a positive integer $n\in \mathbb{N}$ we define the Hadwiger-Nelson graph $\text{HN}_n$ by $V(\text{HN}_n) = \mathbb{R}^n$; $E(\text{HN}_n) = \{\{v_1, v_2\}: v_1, v_2 \in \mathbb{R}^n \text{ ...
2
votes
1answer
85 views

Is a rigid cycle a chordal graph?

There are two relevant questions: (1) We know an edge set $C$ is a rigid cycle in $\mathcal{G}_2(n)$ if and only if $|E(C)|=2|V(C)|−2$ and $|F|≤2|V(F)|−3$ for every proper subset $F$ of $E(C)$. Thus, ...
6
votes
1answer
187 views

A variant to the Hadwiger-Nelson problem

Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$. What is $\chi(G)$? (This is a variant of the ...
0
votes
0answers
14 views

there exists k such that all elements of A^k are positive iff G is bipartite [migrated]

How we can prove this: Suppose G is a connected graph with adjacent matrix A. prove that there exists k such that all elements of A^k are positive iff G is bipartite. Is A^n >0 if G is not bipartite? ...
0
votes
1answer
166 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 ...
7
votes
1answer
362 views

Permutation Group Question

A question about permutation groups: I wonder if someone who is expert in permutation group theory could answer the following question. Let $x \in S_n$ (the symmetric group) be an involution which ...
4
votes
1answer
91 views

Countable hypo-hamiltonian graph

If $G = (V,E)$ is a graph, then a $\omega$-path is an injective map $p:\omega\to V$ such that $\{p(k),p(k+1)\}\in E$ for all $k\in \omega$. In a similar fashion, we define a $\mathbb{Z}$-path. Is ...
-4
votes
0answers
36 views

Hamiltonian Tour with Machine A and B [closed]

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
2
votes
1answer
102 views

Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...
0
votes
1answer
127 views

Ore's theorem for countable graphs

Ore's theorem states that in a finite graph $G$ with $|V(G)|=n$, there is a Hamiltonian path, provided that the sums of the degrees of 2 distinct, non-adjacent vertices is $\geq n$. For countable ...
0
votes
1answer
49 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 ...
3
votes
1answer
209 views

How many hamiltonian paths can be removed from a complete directed graph before it becomes disconnected?

The question started from a problem brought home by a friend's 5th grader: "How many ways you can arrange 5 people sitting around a round table so that the people sitting to the left of any person are ...
2
votes
2answers
119 views

Upper bounds on the edge clique cover number on special graph classes

An edge clique cover of an undirected graph $G$ is a set of cliques of $G$ such that every edge of $G$ is an edge in at least one clique in the set. The edge clique cover number $\theta(G)$ is the ...
5
votes
1answer
286 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 ≥ ...
-4
votes
1answer
58 views

Resources to learn about hypergraphs [closed]

I am working on a project that is based on hyper graphs. Is there any resource that I could refer to understand the basics properties of hyper graphs ?
2
votes
1answer
92 views

Network flows with shared capacities

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as: $$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$ where $f(1, 2)$ denotes the flow through arc $(1, ...
4
votes
3answers
674 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 ...
5
votes
0answers
193 views

When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods. We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...
0
votes
1answer
71 views

A question about graphs not having non-trivial automorphisms [closed]

Let call a simple graph (not containing neither loops, nor multiple edges) "prime", if it has no non-trivial automorphisms, i.e. graph that has only "identity" automorphic transformation. I cannot ...
0
votes
1answer
56 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
2answers
173 views

Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
11
votes
1answer
726 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. ...
15
votes
11answers
1k views

Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...
5
votes
1answer
277 views

Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas. In the following all graphs are simple and connected. Let $G$ be graph with vertex set ...
1
vote
0answers
60 views

Discrete p-Laplacian

One of the definitions of the discrete (weighted) $p$-Laplacian is the following: $$\Delta_{p,w}u(x):=\sum_y |u(y)-u(x)|^{p-2}(u(y)-u(x))w(x,y).$$ Consider the one dimensional case. Then the free ...
31
votes
9answers
3k views

Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors. The purpose of this question is to collect generalizations and strengthenings of the four color theorem ...
3
votes
2answers
154 views

Extremal eigenvalues & eigenvectors of skew-adjacency matrix

I am looking for ways to obtain the extremal eigenvalues and eigenvectors of the skew-adjacency matrix of a directed graph without diagonalizing it. The graphs I am interested in are not regular (but ...
0
votes
0answers
30 views

Least square problems with binary variables

I want to solve the heat equation $T_t(x,t) = - L_x . T(x,t) + F(x,t)$ in an edge-weighted graph where $L_x = \sum_i x_i e_{ij}$ is weighted Laplacian matrix of the graph. Then I conclude to the ...
7
votes
2answers
796 views

Surveys of the items of Erdős' “toolbox”

Could you point out some survey papers and monographs that highlight the kernel of tricks, techniques, and tools that Paul Erdős employed the most in his research work (in particular in graph theory, ...
4
votes
1answer
100 views

Statistics of strongly connected components in random directed graphs

I'm interested in the statistics of strongly connected components in random directed graphs. However, I'm unable to find any results on this, partly because I don't know the terminology to search for. ...
3
votes
1answer
124 views

Condition(s) for the full autormophism group $\operatorname{Aut}(C(G, S))$ of the Cayley graph of $G$ to be isomorphic to $G$

If $\Gamma = C(G, S)$ is the (undirected) Cayley graph of a finite group $G$ with generating set $S$, then $G \le \operatorname{Aut}(\Gamma)$, the "full" automorphism group of $\Gamma$. When is ...
2
votes
2answers
135 views

Term for vertex connected to every other vertex in a graph

Do you know a good common term for the operation of connecting a new vertex v to every vertex in a graph G (or a term for such vertex v)? The ones I know give me poor search results: a nice word ...
2
votes
2answers
80 views

Matching polynomials and Ramanujan graphs

Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts? A $d-$regular graph is said to be called Ramanujan if its adjacency ...
3
votes
1answer
213 views

A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete. I provide two simple definitions and one example at first. Definition 1. Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...
20
votes
5answers
2k views

Complete graph invariants?

Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a ...
10
votes
1answer
1k views

Invariants that might determine graph up to isomorphism

Are there any graph invariants which have a reasonable chance of capturing the graph up to isomorphism? In other words, some candidates for a function $f$ such that $f(G)=f(H)$ if and only if $G$ and ...
8
votes
1answer
154 views

Is the Cayley graph of Thompson's group isolated in the space of vertex-transitive graphs?

Consider Thompson's group (the one commonly referred to as $T$), which is finitely presentable. Consider the Cayley graph, but then forget the coloring and direction on edges. So now we just have an ...
0
votes
0answers
36 views

Discrete bi-Laplacian

I was wondering whether there exists any kind of literature on the the powers of the discrete Laplacian, in particular the the discrete bi-Laplacian, possibly with weights on the edges. In particular ...
7
votes
0answers
60 views

Approximation of the effective resistance on Cayley graph

Let $\Gamma$ be a finitely generated group, and denote by $G$ the Cayley graph of $\Gamma$. Denote by $d_R$ the resistance distance metric on this graph. The resistance distance metric between the ...
12
votes
3answers
727 views

graphs with independence number = Shannon capacity

For $G$ a graph, let $\alpha(G)$ be its independence number and $\Theta(G)=\lim_n \sqrt[n]{\alpha(G^{\boxtimes})}$ its Shannon capacity, where $\boxtimes$ denotes strong product. Consider graphs $G$ ...
0
votes
0answers
29 views

Confusion about reduction counting vertex covers to counting cycle covers

Cross-posted from cstheory This confuses me. One easy case of counting is when the decision problem is in $P$ and there are no solutions. A lecture show that the problem of counting the number of ...
5
votes
0answers
99 views

What's the variance in the Six Degrees model?

Recall the six degrees of Kevin Bacon game. You can even play the game at The Oracle of Bacon, and their search works via Breadth First Search. I interpret the punchline as saying that if I start ...
3
votes
1answer
94 views

Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...