Stack Exchange Network

Stack Exchange network consists of 174 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
19 views

Time complexity of undirected graph

What will be the Efficient way to find the degree of the specified vertex in an undirected graph (V,E)? I'm thinking of O(|E|)
0
votes
0answers
15 views

Hamilton Paths in Complete graph $K_n$

In complete graph $K_n$, is it true that we can have at least $2*n$ Hamilton paths?
1
vote
0answers
17 views

Number of paths in high-girth graphs

In a graph $G$ with girth $g$, say $g = \Omega(\log n)$, can we deduce an upper bound on the number of paths between two nodes $u$ and $v$?
1
vote
0answers
21 views

Tournament bracket for a 4-players game

for Christmas a friend is trying to organize a tournament for 13 players. Each game will be played by 4 persons, each player will play 4 games and must play against everybody else. I can find a ...
0
votes
0answers
13 views

Find Sub-graphs in Random Graph Asymptotically by Expectation and Variance. [on hold]

Definition: Random Graphs Random binomial graphs, $\mathcal{G}=G( n, p):$ This model has two parameters, the number of vertices n and a probability parameter $p \in [0,1].$ Let $\mathcal{G}$ be the ...
8
votes
2answers
80 views

A route that passes through all streets of the city

You are driving a car in a city with $N$ long, straight streets. No two streets are parallel so there is an intersection (crossroads) for each pair of streets. Each intersection has only two ...
0
votes
1answer
22 views

Hamilton path and Euler circuits in Cycle graph

Can $C_n$ has $2*n$ Euler circuits and $3*n$ Hamilton paths in the Cyclic graphs?
0
votes
1answer
17 views

Can we say that vector of branches spans $(n-1)$ dimension space or incidence matrix rows (columns?) span $(n-1)$ dimension space?

If we have connected graph and $\mathbf\Phi=(\Phi_1,\Phi_2...\Phi_n)$ - nodes, and $\phi_k=\Phi_i-\Phi_j$ so $\mathbf{\phi}=(\phi_1,\phi_2...\phi_N)$ - branches (edges), can we say that vector $\...
-1
votes
0answers
20 views

Math logic & graph problem [on hold]

How to prove by using theorem Ehrenfeucht that the connectivity of the graph cannot be expressed by the formula of the first order?
0
votes
0answers
14 views

construction bijection and to understand Dyck path.

In here: https://oeis.org/A080936. I want to understand $T(n,k)$ is the number of Dyck paths of semilength $n$ and height $k$ and following triangle. \begin{align} 1;\\ 1, & 1;\\ 1, & 3, 1;\\ ...
2
votes
3answers
32 views

Visual example of an infinite planar graph with degree sequence $(4^4,6^\infty)$

After reading some graph theory and talking with experts, I was intrigued. I would like to construct and visualise an infinite planar graph with degree sequence: $$D=(4^4,6^\infty)$$ where the ...
-1
votes
0answers
18 views

Distance-transitive graphs

The distance-transitive graphs are classified for diameter at least 5? Is this J.V. Bon, Finite primitive distance-transitive graphs, European J. Combin., 28:517– 532, 2007, the right reference? Or ...
0
votes
1answer
32 views

How to find a minumum vertex cover from a maximum matching in a bipartite graph?

Konig's theorem states that for a bipartite graph the number of vertices in the minimum vertex cover equals the number of edges in a maximum matching. https://en.wikipedia.org/wiki/K%C5%91nig%...
0
votes
0answers
32 views

Number of Perfect Matching in Complete Graph - Proof Explanation

Want to find the number of perfect matching in a complete graph K2n where 2n is the number of vertices: Came up with the following method - 1. Counting Edges ...
1
vote
1answer
28 views

Degree of quotient graph of a regular graph

What can we say about the degree of a quotient of a regular graph? Intuitively, I think the situation may get arbitrarily bad. Specifically, I am looking for an example of an infinite family of $k$-...
0
votes
1answer
19 views

A lower bound for the number of triangles that contain a particular edge

If $u \leftrightarrow v$ in a graph $G$, prove that $uv$ belongs to at least $d(u) + d(v) − n(G)$ triangles in $G$, where $n(G)=$ number of vertices in $G$. In this question, I tried a lot. I know we ...
5
votes
1answer
58 views

What is the fastest route to drop off weight when time is proportional to weight x distance?

You have a lorry at the starting point which is carrying all the parcels for the day. $$\rm Time\ taken = Total\ Lorry\ Weight \times Distance\ travelled $$ After visiting each zone you have to ...
0
votes
1answer
18 views

Counting the directed paths in a particular directed graph /runtime

My question is: How much time does a computer need, who compares the length of $10^9$ different paths within a second, to find the shortest way in the following graph $ G=(V,E)$ for n=100. $$\begin{...
0
votes
1answer
41 views

Expected Number of edges in the graph

G(V,E) is a simple graph with 8 vertices. The edges of G are decided by tossing the coin for each 2 vertices combination. Edge is added between any two vertices iff head is turned up. Expected number ...
1
vote
1answer
22 views

Question - Chromatic Polynomial for Given Graph

I am trying to find the chromatic polynomial for the graph below: I am using the inclusion-exclusion principle. Here are my bad cases: $A_1 = \{1 \text{ and } 2 \text{ colored the same }\}$ $A_2 =...
0
votes
1answer
9 views

Drawing Graph of trigonometry Imaginary angle [on hold]

What wold be The Graph of cos ,sin or anything of an imaginary angle?Will it be in X-Y Or X_Y-Z plane?
2
votes
3answers
40 views

How to draw a graph that represent this problem? Using a $5$-liter bottle and a $3$-liter bottle to arrive at exactly $4$ liters of water.

You have 2 water bottles, a 5l bottle and a 3l bottle. If the bottle is empty, You can fill it up fully at the tap. If the bottle is full, You can empty the bottle. You can transfer the ...
0
votes
1answer
14 views

Find an edge subset such that the graph is bipartite.

Let $G$ be a undirected Graph. Find the minimal subset of edges $F$ such that $G$ without $F$ is bipartit. Prove that this is possible in linear time, meaning Number of Nodes + Number of Edges. I ...
0
votes
1answer
13 views

Matching of size at least $\frac{|E(G)|}{3}$ in the line graph $L(G)$ of a graph $G$

Let $G$ be a loopless graph such that the degree of every vertex is even . Show that the line graph $L(G)$ of $G$ contains a matching of size at least $\frac{|E(G)|}{3}$. My attaimpt: By a theorem ...
-1
votes
1answer
24 views

Exercise 2.1.19 in An introduction to expander graphs by E. Kowalski

I am trying to prove an exercise saying that the girth of a finite graph Γ with minimum valency $\geq 3$ is $≪ log(|Γ|)$. But I have no idea to do that. Could please help me to prove it.
0
votes
0answers
11 views

Sampling probabilities for half-sparsification algorithm

https://dl.acm.org/citation.cfm?id=2948062 In their article(simple parallel and distributed algorithms for spectral graph sparsification 2016), Koutis and Xu gave a combinatorial algorithm for ...
1
vote
1answer
20 views

Unique path in a connected graph

An undirected connected graph with $n - 1$ edges has only one unique path between any 2 vertices. Is this true. If so, how.
1
vote
1answer
14 views

Help in solving a question to trace the perimeter of a face in a polyhedron

I have the following question with me: "We assign an arrow to each edge of a convex polyhedron, so that at least one arrow starts at each vertex and at least one arrow arrives. Prove that there exist ...
4
votes
1answer
43 views

Counting the directed paths in a particular directed graph

I want to find out how many directed simple paths from $s$ to $t$ are in the following directed graph $G=(V,E)$. $$\begin{align} V=&\{s, v_1, v_2,\ldots, v_n, t\}, \quad n=2k, k \in \mathbb{N} \\ ...
1
vote
0answers
22 views

Is there a way to present all possible combinations for a given sequence on a grid-like space?

Specifically, my curiosity is in relation to the traveling salesman problem. I know that if you're on a 2D graph, you can represent the distance between cities using linear distance; I'm asking ...
2
votes
0answers
18 views

Diameter of a set in the discrete cube

Let $[n] = \{1, \dots, n\}$. Define the discrete cube $Q_n$ to be the graph with vertex set $\mathcal{P}([n])$ such that $x,y \in \mathcal{P}([n])$ are adjacent iff $|x \triangle y| = 1$ On the ...
4
votes
1answer
46 views

How to find the Euler characteristic of a cellularly embedded graph, given only the vertices and edges?

Suppose that we are given a finite connected graph, i.e. the finite vertex set $V$ and a finite edge set $E\subseteq P(V)$. Is there an algorithm to find the Euler characteristic of any cellular ...
-1
votes
1answer
43 views

Number of isomorphisms between two graphs

I'm studying for an exam in graph theory, and this question came up. The question is: how many isomorphisms exist between these two graphs. I know that, as they are isomorphic, this is the same as ...
0
votes
1answer
26 views

Check if the graph is bi-partite [on hold]

Let $G$ be the graph whose vertex set is the set of $k$-tuples with coordinates in $\{0, 1\}$, with $x$ adjacent to $y$ when $x$ and $y$ differ in exactly one position. Determine whether $G$ is ...
-1
votes
1answer
27 views

how to use the pigeon hole principle on a graph problem? [duplicate]

I have this given problem: In a class there is 6 students,every 2 students of 6 know each other in advance or they don't. Show that there is 3 students that don't know each other in advance or that ...
1
vote
1answer
14 views

$\epsilon$-regular pairs

Suppose $G$ is a graph and $A,B$ are subsets of its vertex set. Given some $\epsilon >0$, the pair $(A,B)$ is called $\epsilon$-regular if for every $A'\subseteq A$ and $B'\subseteq B$ such that $|...
0
votes
0answers
22 views

A Hamilton graph having a Hamilton cycle that traverse an edge more than once.

I was asked to draw a Hamilton graph having a Hamilton cycle that traverse an edge more than once. My first impression of this question was: what? I mean if we are not allowed to visit a vertex more ...
2
votes
1answer
26 views

Optimal Tree Labelling

I am trying to solve the following problem : For a tree $T = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges. A label $L$ of $T$ is an application from $T$ to $\{0,1\}^{|V|}$. ...
1
vote
0answers
32 views

Number of subgraphs of a triangle

I'm having difficulty finding the number of subgraphs of a triangle... the solutions of the textbook I'm using says the answer is $18$, but I am counting $17$ in the following way: $$\binom{3}{1}\...
0
votes
0answers
27 views

Distinct Minimum Weight Spanning Trees

I am trying to find the total number of distinct minimum weight spanning trees(MWST) in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider ...
2
votes
1answer
19 views

Graph whose smallest edge clique cover is not the collection of all maximal cliques

Let $G$ be an undirected simple graph. An edge clique cover of $G$ is a collection $\mathcal{C}$ of cliques (i.e., complete subgraphs) that cover all the edges of $G$. In other words, every edge ...
0
votes
0answers
17 views

Number of returns simple random walk $\mathbb{Z}^d$

I am interested to know the precise numerical value of the expected number of returns to the origin of a simple random walk on $\mathbb{Z}^d$, when $d \geq 3$. Does anyone know where I can find such a ...
0
votes
3answers
28 views

Prove that the thickness of $K_6$ is $2$. (That is, find two graphs $G$ and $H$ such that $G∪H = K_6$ and $G$ and $H$ are both planar.) [on hold]

Prove that the thickness of $K_6$ is $2$. (That is, find two graphs $G$ and $H$ such that $G\cup H =K_6$ and $G$ and $H$ are both planar.)
0
votes
0answers
22 views

Definition of closed walks on a graph. How to enumerate the vertices?

In my definition, this is a closed walk? If yes, how can I enumerate the vertices? In this picture, who is $v_1, v_2,...$? Definition: A closed walk in a graph is defined to be ordered collection of ...
3
votes
1answer
58 views

Finding a subdivision of $K_4$ in a graph with minimum degree $3$.

In the Bondy and Murty's graph theory book there is the following exercise. Let $G$ be a nontrivial simple graph with $\delta(G)\geq 3$ or a vertex $v\in V(G)$ such that $\delta(G-v)\geq 3$. Then $...
-1
votes
0answers
26 views

Find a minimal closed walk that visits every vertex of the graph at least once (loops are allowed) [on hold]

For all finite connected graph, how can I find a minimal closed walk that visits every vertex of the graph at least once? Obs.: Loops are allowed
-2
votes
0answers
21 views

Problem of Compactness Theorem [on hold]

There is a set of squares with partitions (walls) between some cells inside them is given. It is known that any square can be paved with these squares so that there is a path from the upper side to ...
1
vote
1answer
22 views

Modelling of a flow network with a positional constraint

While I do realise pasting an exercise question in here is not exactly perfect form, I am desperate and I wil try anyway. So here it goes: Consider a set of n mobile computing clients in a town with ...
0
votes
0answers
22 views

Is there any operation involved related to closure of a graph? What is the motivation behind defining closure of a graph?

Do we always use the word closure under some operation? Usually, I have used the word closure as the set we get after adding element in a set to make that set self content under some operation. For ...
0
votes
1answer
26 views

Making column sum of adjacency matrix even.

Let $G$ be a connected graph with $V$ vertices and let say I have an adjacency matrix of order $N$, how can I make sum of each column even? Like I have a graph with $4$ vertices and $4$ edges as $\...