Questions tagged [graph-theory]

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, topological-graph-theory, random-graphs, graph-colorings and several others.

Filter by
Sorted by
Tagged with
1
vote
1answer
24 views

Bandwidth of two-dimensional grid graphs

Suppose that $G$ is a subgraph of the two-dimensional grid and there are $n$ vertices in $G$. What is the maximum possible graph bandwidth of $G$ as a function of $n$? If $G$ is a square grid graph ...
-4
votes
0answers
26 views

how to find out a node that is not reachable from other nodes in a list and then add an edge b/w that node and a random node in python [closed]

I have an adjacency matrix of graph G=(V,E) and a list of nodes 'v' subset of V. Now I want to find out node/nodes of 'v' that is/are not reachable from other nodes of 'v' and then adding an edge ...
-1
votes
1answer
56 views

Effect of collapsing two vertices of distance $2$

Motivating example. Consider the graph $G=(V,E)$ with $V = \{0,1,2,3\}$ and $E = \big\{\{i,i+1\}: i\in \{0,1,2\}\big\}$. We have $\chi(G) = 2$, but if we collapse $0$ and $3$, we get the complete ...
0
votes
0answers
41 views

De Morgan applications for Graphs [closed]

$\DeclareMathOperator\comp{comp}$Are the De Morgan laws applicable for simple graphs? For example if I know that certain operations like Union, Intersection and Complement are working for $G$ and $H$ ...
0
votes
0answers
21 views

Clustering coefficient in a directed graph

I am wondering what the meaning of the clustering coefficient in a directed graph. I know how to calculate it: local clustering coefficient formula, retrieved from [Wikipedia]1 and I know how to ...
0
votes
1answer
30 views

Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques

Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
1
vote
0answers
24 views

Finding minimum weight perfect matchings in sparse bipartite graphs

Question: What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values? I am looking for ...
7
votes
1answer
368 views
+50

Boundedness of total current in electrical network

Consider the following symmetric matrix (adjacency matrix): $$A=(a_{ij})_{1\leq i,j\leq n}$$ such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...
1
vote
0answers
40 views

What is known about this generalization of planar dual?

So it is well known that given a planar graph, $G$, embedded in the plane (without edge crossing, so a planar embedding). One can construct the planar dual, $G^*$. What is perhaps slightly less well-...
1
vote
1answer
130 views

Cayley graphs do not have isolated maximal cliques

Let a Cayley graph $G$ of a group $H$ with respect to the generating set $\{s_i\}$ have a clique of order $> 2$. In addition assume the graph $G$ is non-complete. If the clique size is less than ...
11
votes
2answers
280 views

Exponential decay of voltage potential difference

Consider the following adjacency matrix of a complete graph: $$A=(e^{-|i-j|})_{1\leq i\neq j\leq n}$$ with 0 on the diagonal. Let $D=diag\{d_1,...,d_n\}$ be the degree matrix where $d_i=\sum_{j\neq i}...
1
vote
0answers
54 views

What is the standard definition of dual of disconnected planar graph when underlying graph derives 'product structure' over connected graphs?

Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph? Update ...
57
votes
28answers
5k views

Proofs where higher dimension or cardinality actually enabled much simpler proof?

I am very interested in proofs that become shorter and simpler by going to higher dimension in $\mathbb R^n$, or higher cardinality. By "higher" I mean that the proof is using higher dimension or ...
0
votes
0answers
29 views

Average number of edges of an induced graph by using the edge-based node selection technique on a graph with arbitrary degree distribution

Let $G(U,V,E)$ be a simple, undirected, bipartite graph and $U=\{u_1,u_2,{\cdots},u_n\}$ and $V=\{ v_{1},v_{2},\cdots,v_{n}\}$. Let $d_k^l$ be the number of vertex with degree $k$ in $l$, where $l \in ...
2
votes
1answer
57 views

Critical probability for Erdos-Renyi digraphs to be strongly connected

Given $p \in [0,1]$, an Erdos-Renyi graph ${ER}(n,p)$ on $n$ vertices is constructed by defining, for each unordered couple of distinct vertices ${i,j}$ an edge between $i$ and $j$ with probability $p$...
1
vote
0answers
10 views

maximal k-partite subgraph in a complete multipartite graph

What is the maximum number of edges a $k$-partite subgraph of a complete $s$-partite graph can have? Bests, Josefran
1
vote
1answer
143 views

Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]

If so, could you provide examples and specify the conditions under which this occurs? Thank you in advance
3
votes
0answers
158 views

Probability that a random multigraph is simple

Question. Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
1
vote
1answer
86 views

Explanation of a proof of an embedding lemma of Bollobas and Thomason

I do not understand the proof of Bollobas and Thomason of an embedding lemma. There is a lot of notation to present first, then the statement of the lemma, then the precise question about the proof. ...
7
votes
0answers
247 views

Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?

Is the following lemma a well known result in graph theory? I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
2
votes
0answers
23 views

Automated rewriting of string diagrams in symmetric monoidal categories

Many algebraic structures, such as Frobenius algebras, or quasi-triangular Hopf algebras, can be formulated in an arbitrary symmetric monoidal category. They are given by a collection of morphisms, ...
2
votes
0answers
32 views

eigenvectors of a graph Laplacian VS Fourier basis

Could you please illustrate the following statement: the eigenvectors of a graph Laplacian behave similarly to a Fourier basis, motivating the development of graph-based Fourier analysis theory.
0
votes
1answer
54 views

Max weighted matching where edge weight depends on the matching

Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
3
votes
1answer
62 views

The effects of collapsing vs joining non-adjacent vertices on the chromatic number

For any set $X$, let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$. Is there a finite, simple, undirected, connected graph $G=(V,E)$ with the following properties? There is $\{v, w\}\in [V]^2\...
0
votes
0answers
10 views

Finding weight minimal swap-free directed vertex covers

Suppose a complete directed graph is given with $n$ vertices and $n(n-1)$ weighted arcs $a_{ij}$ and we have $\omega(a_{ij}\ne\omega{a_{ji})$ for at least one pair of antiparallel arcs and the ...
2
votes
0answers
114 views

Graphs which are built from complete graphs : Reference request

Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$. We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be ...
2
votes
0answers
42 views

The expected size of a subtree of any labelled rooted tree

Consider the set of labelled rooted trees of size $n$, $\mathcal{T}_n$. Let $r$ be the root of each tree $T=(V,E)\in\mathcal{T}$, $r\in V(T)$, and let $n(u)$ be the number of vertices of the subtree $...
0
votes
0answers
42 views

Lower bounds on the length of circuits, depending on the number of times it crosses itself

I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below. Let $G(V,E)$ be ...
1
vote
0answers
43 views

Support of random closed walk in arbitrary graph

Researching a question related to closed walks on graphs, I have come across the following problem. Let $G$ be a connected graph on $n$ vertices and $k=O(\log(n))$. Pick a random closed walk on $G$ as ...
0
votes
0answers
16 views

Order-relational conditions for 4 points being in convex configuration

In the euclidean plane a simple sufficient condition for 4 points being in convex configuration is as follows: if the points are $\lbrace A,\,B,\,C,\,D\rbrace$ of which $\lbrace A,\,B,\,C\rbrace$ are ...
1
vote
0answers
38 views

Gromov-Hausdorff distance between graphs with edges as part of the space versus not part of the space

Let $G_1$ and $G_2$ be finite simple graphs viewed as metric spaces in the natural way where the edges are not part of the space. Let $G_1'$ and $G_2'$ be copies of $G_1$ and $G_2$ resp. but with the ...
0
votes
1answer
69 views

Value (not position)- based sorting; reference request

A recent answer of Ville Salo on the diameter of a Cayley graph induced by bubble sort generators (adjacent transpositions) has inspired this variation. Many sort algorithms are position based: you ...
0
votes
0answers
57 views

Expected number of directed cycle in a directed complete graph

Consider the randomized, directed complete graph G = (V, E) where for each pair of vertices u, v ∈ V, we add either the directed edge (u → v) or the directed edge (v → u) chosen uniformly at random. ...
1
vote
1answer
71 views

Outer automorphism group of $F(G)$

By a nice helpful comment in my last question, I see that if $\Phi(G)=1$ then ${\rm Out}(F(G))$($\cong G/F(G))$) is isomorphic to a direct product of ${\rm GL}(n_i,p_i)$. Actually, I’m digesting an ...
0
votes
0answers
37 views

Antimagic labelings to prove total coloring conjecture

An antimagic labeling of a simple graph with order $n$ and size $m$ is a surjective function from the set of edges to a set of labels (numbers) of size $m$ such that the sum of labels of the edges at ...
2
votes
0answers
40 views

Can a polytope with vertex-transitive edge graph or face lattice be made vertex-transitive?

Let $P\subset\Bbb R^d$ be a convex, full-dimensional polytope (convex hull of finitely many points, affine hull is the whole space), $G_P$ its edge graph and $\mathcal F_P$ its face lattice. Any of ...
1
vote
1answer
61 views

Distance pairs in labeled directed graph

Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum ...
7
votes
1answer
292 views

Natural $\Pi_1$ sentence independent of PA

Order invariant graphs and finite incompleteness by Harvey Friedman gives an example of a combinatorial/non-metamathematical $\Pi_1$ sentence that is independent of ZFC. Is there a simpler example of ...
11
votes
2answers
561 views

Which curves and surfaces are realizable by linkages? references?

Ok, so I try to formulate rigorously the question in the title, for which I am asking for references. My definitions may be flawed, so feel free to adjust/correct them! I care about dimensions 2 and 3 ...
3
votes
1answer
74 views

Graph structure on $S_\omega$ induced by fixed points on compositions

Let $S_\omega$ denote the collection of bijections $f:\omega\to\omega$. We say that $f \in S_\omega$ has a fixed point if there is $x\in \omega$ with $f(x) = x$. It is a short exercise to show that ...
14
votes
2answers
453 views

A tree with prime vertices

Let us construct a simple (undirected) graph $T$ as follows: $\quad$ Let the set of all primes be the vertex set of $T$. For each prime $p$, take the least prime $q>p$ such that $2(p+1)-q$ is ...
4
votes
1answer
88 views

“Total rainbow” trees

Let $G= (V,E)$ be a simple finite graph which is (not necessarily properly) edge-colored. A rainbow spanning tree refers to a spanning tree T of G such that no color appears more than once amongst the ...
1
vote
0answers
24 views

Clustering number on ring lattice

I have seen in several places a useful formula that let us calculates the clustering number of regular ring lattice graphs with even degree but I have not found a convincing proof of it. Concretely, ...
8
votes
1answer
103 views

What graph's minimum vertex cover equals twice the maximum matching?

Matching: https://en.wikipedia.org/wiki/Matching_(graph_theory) Vertex Cover: https://en.wikipedia.org/wiki/Vertex_cover It is easy to see that $$\texttt{minimum vertex cover} \leq 2 \texttt{ ...
1
vote
0answers
38 views

Count shortest path with different lengths in random graph

Let $G(n,p)$ be an Erdos-Renyi random graph on $n$ vertices with probability $p$, i.e. for each pair of vertices, they are connected directly by an undirected edge with probability $p$. Suppose we are ...
4
votes
0answers
42 views

If all 2-faces of a polytope are $2n$-gons, is the edge-graph bipartite?

This question on MSE has not received a satisfying answer. It can be summarized as follows: Question: Is is true that the edge-graph of a (convex) polytope is bipartite if and only if all 2-faces ...
22
votes
1answer
419 views

Doubly periodic 4 color theorem?

Let $G$ be a graph embedded (without crossings) on a torus $T$. It's fairly well known that this implies the chromatic number of $G$ is at most 7. If I lift $G$ to the universal cover of $T$, we get a ...
0
votes
0answers
25 views

Enumerating all directed 3-cycle covers

It is fairly easy to enumerate the directed Hamilton cycles of a complete directed graph by fixing one of the vertices and enumerating the permutations of the others via one of the next-permutation ...
5
votes
2answers
100 views

Is the acyclic chromatic number bounded in terms of the book thickness?

ISGCI says that the chromatic number of a graph is upper bounded in terms of the book thickness. https://www.graphclasses.org/classes/par_32.html This can be improved by saying that the book ...
5
votes
2answers
263 views

Transposition Cayley graphs are planar

Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13)...

1
2 3 4 5
79