Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

0
votes
0answers
12 views

Update an existing route with a set of pedestrian crossings

I am trying to route though a set of pedestrian crossings. I ask a route to some location service to get a default route, the problem with that route is that it does not include some waypoints (...
0
votes
1answer
11 views

Graph theory: plex and clique

How do a 2-plex relates to a 2-clique? I think that being a 2-plex means that is also a 2-clique but i don't know how to prove it. Thanks,
0
votes
0answers
19 views

Number of eulerian paths in an undirected connected graph between two given vertices?

Given a undirected connected graph G(V, E). Provide an optimal algorithm, which finds the number of eulerian paths between vertex 1 and vertex |V|. I was thinking about matrix multiplication, but I ...
0
votes
0answers
10 views

ST-CON variation: is it also in NL?

Consider the following variation on the ST-CON decision problem: given a directed graph $G$, for every two different vertices $s$ and $t$, there is a directed path between $s$ and $t$. Intuitively, it ...
0
votes
0answers
21 views

If $d^{+}(v)=1$ for all v in a connected graph $G$, then show G has exactly one circuit.

If $d^{+}(v)=1$ for all v in a (weakly or strongly) connected graph $G$, then show G has exactly one circuit. Let G has n vertices. Number the vertices $1,2,...,n$ Since G has n edges, and WLOG $1,2,....
0
votes
1answer
20 views

Sorting vertices by Minimum Spanning Trees in a forest of MSTs

Consider a number of vertices. They are separated into a number of Minimum Spanning Trees (MSTs) (so there's a forest of MSTs) using Kruskal's algorithm. For each vertex I need to know in which MST ...
1
vote
0answers
25 views

What is basic graph of a graph?

I am not quite sure myself, hence I try to ask if I may. I read some papers which say something about the basic of a graph. Generally, what does it mean for a graph $G$ to be the basic of the graph $...
1
vote
1answer
30 views

Number of ordered trees of size $n$

I'm trying to solve a problem related to counting the number of trees. Basically, I want to count trees as different only if they have different structure. So, for example, there are $5$ trees of ...
0
votes
0answers
33 views

Prove that every planar graph is the union of at most $5$ acyclic graphs.

Prove that every planar graph is the union of at most $5$ acyclic graphs. Reminder: As union of two graphs $G_1(V_1, E_1)$ and $G_2(V_2, E_2)$ we consider the graph $G(V_1\cup V_2,E_1\cup E_2)$ ...
0
votes
0answers
17 views

Path between nodes in a colored oriented tree with given weight sum

Consider an oriented tree where each node is colored either black, white, or both. In addition, each (oriented) edge has a given weight. I am trying to see whether there exists a pair $(u, v)$ of ...
1
vote
0answers
16 views

Is it okay to not provide a whitelist when using the Hill-Climbing algorithm?

So, I'm trying to use Hill-Climbing for a Bayesian learning network. For some reasons, I do not know all of the variables that I'm going to use and hence, I cannot provide a whitelist or a blacklist ...
1
vote
1answer
27 views

Every cubic 3-connected Hamiltonain graph has three Hamiltonian cycles with special property

It is known that every cubic Hamiltonian graph has at least three Hamiltonian cycles (by Tutte's theorem that every edge of a cubic graph belongs to an even number of Hamiltonian cycles) It is true ...
2
votes
1answer
46 views

Knightwise Connectedness of a Chessboard Fragment

Define the “Knightlyness” of a square on a chessboard fragment as the number of squares on that fragment that a knight could jump to in one move from the square under consideration. The “average ...
1
vote
1answer
44 views

A problem from Germany [on hold]

Every road in Sikinia(city) is one-way. Every pair of cities is connected exactly by one direct road. Show that there exists a city which can be reached from every city directly or via at most one ...
3
votes
0answers
14 views

Spanning forests of bipartite graphs and distinct row/column sums of binary matrices

Let $F_{m,n}$ be the set of spanning forests on the complete bipartite graph $K_{m,n}$. Let $$S_{m,n} = \{(r(M), c(M)), M \in B_{m,n} \}$$ where $B_{m,n}$ is the set of $m \times n$ binary matrices ...
2
votes
1answer
29 views

Hamiltonian and Eulerian graph with 2 bridges?

Is it possible to have graph which is Hamiltonian and Eulerian at once with 2 bridges in it? If yes, how can it look like? Thank you. Edited: The bridge is an edge of a graph whose deletion ...
-2
votes
1answer
37 views

Bounding the number of edges in a graph satisfying a certain property

I am going through past papers because I am revising for my Graph Theory exam this week. I encountered the following question: The bipartite Ramsey number $R(s,t)$ is the minimum $n$ s.t. a ...
-1
votes
1answer
23 views

Clique number and maximum clique of gcd-based graph

This is from my homework. Let $Q_n$ be the graph with vertex set $\{1, 2, \ldots, n\}$. Two vertices are adjacent if and only if their greatest common divisor is $1$. Give the clique number of $Q_{...
-1
votes
2answers
38 views

How to find the number of x-length walks between two vertices of a triangle

This question is from my homework and I don't have any idea how to solve it. Find the number of 2019-length walks between two vertices of a triangle.
0
votes
1answer
29 views

Non-isomorphic graphs with same Tutte polynomial

I've been looking for some non-isomorphic graphs with the same Tutte polynomial. I'm aware of this thread and this thread, however my understanding of matroids is non-existent, and they are a bit ...
7
votes
1answer
54 views

Graph with the condition that every vertex is connected to at least n other vertices.

Problem: (Adrian Tang) $G$ is a graph with $2n+1$ vertices. In $G$, for every set $S$ of at most $n$ vertices, there is one vertex outside of $S$ that is adjacent to every vertex in $S$. ...
-1
votes
0answers
17 views

Trees are a X of graphs [on hold]

The set of all trees (of size n) would be called a subset of all graphs (of size n). What is the nomenclature of the relation between trees and graphs? Could one say trees are a subclass of graphs? A ...
0
votes
0answers
39 views

Prove that if k is odd and G is a k-regular (k-1)-edge-connected graph, then G has a perfect matching.

I understand that if k is odd and G is k-regular, then each vertex must have odd degree. I am having trouble understanding how to incorporate the edge-connectivity. (This is my first undergraduate ...
0
votes
0answers
31 views

Finding the number of edges of a triangulation of a polygon on n vertices

I am faced with the following question: A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon and all of whose other faces are triangles. How many edges does a ...
0
votes
1answer
44 views

Prove $R(t,t) \ge 2^{t/2}$ for all $t\ge 3$

Prove $R(t,t) \ge 2^{t/2}$ for all $t\ge 3$. I'm thinking about using induction. Base case: R(3,3)=6, which works. Inductive Step: I claim $\frac{R(t+1,t+1)}{R(t,t)} \ge \sqrt{2}$, which is true ...
1
vote
1answer
52 views

How to understand the structure of the interesting graph obtained from the group?

Let $G = A_5$ and $H < G$ is subgroup of $A_5$ generated by $(12)(34)$, and $(125)$. Define graph $\Gamma$ by a vertex set is element of $G$ and elements $x$ and $y$ adjacent if $|H^x \cap H^y| =...
0
votes
0answers
16 views

Coloring of hypergraph with polynomial implication

Sorry to bother again with my misunderstandings, but I encountered yet again an issue with the topic of coloring in graphs and again I require some help to deal with this exercise: Let $\mathbb{F}$ ...
0
votes
1answer
19 views

Can a $k$-regular graph with $99$ vertices $(G=(99,E))$ be a bipartite graph?

I was reviewing some exams from previous years on Graph Theory and I'm stuck on this question. What I have so far is that for a graph to be bipartite, we need to have $2$ subsets of $V=99$ $(G=(V,E)...
0
votes
1answer
27 views

Does edge contraction increases the degree of a regular graph

Definition: A contraction of an edge represents the merging of the coalitions associated to its incident vertices. Definition: A graph G is said to be regular, if all its vertices have the same degree....
1
vote
3answers
45 views

Prove that a NxN grid can be colored using n colors such that each color appear once each row and column

Just like a simpler Sudoku game, given n, show that nxn grid can be colored using n colors so that each color appears once for each row/column. I see that each row/column forms a complete graph so ...
0
votes
0answers
6 views

Timetable representations and implementations in graph databases

I have seen that in graph-theory timetables (for example the ones of public transports) and more in general time-varying edges can be typically represented in two ways. One way is the time expanded ...
0
votes
0answers
35 views

Self-study Graph theory

I decided to self-study graph theory. I am not newbie in it as I have experience from programming, like I know graph algorithms and how they work, have some experience with discrete mathematics(well, ...
5
votes
1answer
40 views

The chromatic number of a graph is at most its circumference

The chromatic number of a graph is at most its circumference: the length of the longest cycle in the graph. (Making an exception for forests, where the chromatic number is at most $2$ and the ...
-1
votes
2answers
19 views

Prove that a directed graph with no cycles has at least one node of indegree zero

How would I show this? I know a directed graph with no cycles has at least one node of outdegree zero (because a graph where every node has outdegree one contains a cycle), but do not know where to go ...
1
vote
2answers
43 views

Knowing every odd circuit in a graph is a triangle, prove $\chi(G) \le 4$ [duplicate]

Knowing every odd circuit in a graph is a triangle, prove $\chi(G) \le 4$ My approach: an odd circuit requires 3 colors, and an even circuit requires 2. But then I'm stuck. Can you give me a hint on ...
0
votes
0answers
14 views

Build a graph with uniform distribution [on hold]

I have 1000 points with (x,y,z) coordinates. From each node, beginning from (0,0,0) coordinates, 4 branches may be progressed to other nodes. The length of each branch should be less than ...
0
votes
1answer
21 views

Confusion about the definition of a graph property and it's relation to $G(n,p)$

We defined a graph property the following way: Let $\Omega_n$ be the set of all graphs $G = ([n], E)$ on $n$ nodes. Then, a graph property is a sequence $P = (P_n)_{n \in \mathbb N}$ with $P_n \...
2
votes
0answers
29 views

Spectral measure of a finite graph

Let $A$ be the adjacency operator of connected, locally finite graph $G = (V,E)$ ($A$ seen as an operator on $\ell^2(V)$). Then we have the spectral representation $$ A = \int_{\sigma(A)} t \mu(dt)$$ ...
1
vote
0answers
21 views

Minimal one-step distance set of vertices to all vertices

I want to find minimal set of vertices such that every vertex in this graph either in this set or connected with some vertex from this set with one edge. Is there standard name for this algorithm? It ...
0
votes
1answer
23 views

edge deletions and spanning subgraphs

The following is from Graphs and Digraphs 6th Edition by Chartrand, Lesniak and Zhang: For a vertex $v$ and an edge $e$ in a nonempty graph $G = (V, E)$, the subgraph $G-v$, obtained by deleting $...
1
vote
1answer
18 views

Chromatic index of planar 4-regular graphs

Planar graphs of max degree 4 are, in general, not necessarily edge-4-colorable. However, what is the situation if the graph is 4-regular, is it edge-4-colorable? I am guessing this is known ... ...
3
votes
1answer
55 views

Can you prove $K_{3,3}$ is not planar without the Jordan Curve Theorem?

The non-planarity of $K_{3,3}$ is well know and e.g. shown here: 3 Utilities | 3 Houses puzzle? However, it is pointed out that the given proofs all use the Jordan Curve Theorem in one form or ...
1
vote
1answer
26 views

$G$ is a forest if and only if every connected subgraph is induced

G is a forest -> every connected subgraph of G is induced Definition of a induced subgraph: for x,y in V(F), xy is in E(F) if and only if xy is in E(G) Proof: Be F a connected subgraph of G. Suppose ...
1
vote
0answers
12 views

Name for a digraph having at most one path between any 2 nodes?

I have used the notion of a directed graph which has at most one path between any two nodes (examples: trees, complete bipartite graph) in a research paper on a topic only tangentially related to ...
1
vote
0answers
16 views

Number of permutation matrices within a distance of a given matrix

Given a matrix $M$, and a permutation $P_0$, is it possible to easily count, or easily approximately count, the number of permutation matrices $P$ that satisfy $\|P - M\| = \|P_0 - M\|$? What about ...
0
votes
0answers
16 views

Compute the shortest path in a directed acyclic graph

Problem: Let $D = (V,A)$ be a directed acyclic graph, i.e., there exists no directed cycle in D, and let $w : A → R$ be arc weights. Assume that you are given a topological sort of the vertices. Show ...
0
votes
0answers
21 views

Bichromatic graph

There is a complete bichromatic graph with shares of 300 and 500 vertices. What is the minimum number of colors in which edges and vertices can be painted in such a way that there are no: 1) ...
0
votes
0answers
28 views

Expectation of number of hubs in a random graph

Suppose $\Gamma(V, E)$ is a finite simple graph. Let’s call a vertex $v \in V$ a hub if $deg(v)^2 > \Sigma_{w \in O(v)} deg(w)$. Here $deg$ stands for the vertex degree, and $O(v)$ for the set of ...
0
votes
2answers
23 views

Find number of leaves of a tree (Proof)

Problem: Let $T$ be a tree that has $i\ge1$ branch nodes, all of which have the same degree[1] $d$. Show that the number of leaves $(l)$ of the tree can be calculated via the following formula: $$l=(...
2
votes
0answers
49 views

The spectral radius of Markov's averaging operator for the lattice graph $\mathbb{Z}^n$ is $1$

The spectral radius of Markov operator for the lattice graph $\mathbb{Z}^n$ is $1$ The lattice graph $\mathbb{Z}^n$ is defined as $V=\mathbb{Z}^n , E=\{ \{\vec{x} , \vec{y}\} : \vec{x},\vec{y}\in \...