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.

learn more… | top users | synonyms

0
votes
1answer
28 views

Need help understanding a proof (Bipartite Graph)

I was reading lecture notes of graphs(from MIT 6042) and am having trouble understanding this proof: I can't understand ...
4
votes
0answers
18 views

labelled graph characteristic polynomial

Given the adjacency matrix $\mathbf{A}$ for a simple connected graph, the characteristic polynomial is defined as: $$ p(\lambda) = \det(\lambda \mathbf{I} - \mathbf{A})$$ Now if an edge between ...
0
votes
0answers
15 views

Euler path for directed graph?

How do we find Euler path for directed graphs? I don't seem to get the algorithm below! Algorithm To find the Euclidean cycle in a digraph (enumerate the edges in the cycle), using a greedy process,...
1
vote
2answers
41 views

How many labeled trees exist with vertices $\{1,2,3,4,5\}$ that contain the edge $\{1,2\}$? [on hold]

How many labeled trees exist with vertices $\{1,2,3,4,5\}$ that contain the edge $\{1,2\}$?
0
votes
1answer
24 views

Counting the number of Eulerian trails in a connected, directed graph

I can't find anything about this online, and I'm beginning to suspect it's a hard problem. I know that counting the number of circuits is #P-complete, but I don't need the number of circuits; I need ...
1
vote
1answer
384 views

Graph nomenclature

This concerns graphs that are sets of vertices and edges G={V,E}, not graphical depiction of functions. Imagine a graph that is a 2D square mesh of vertices. Such a graph can be constructed, for ...
0
votes
0answers
15 views

Plane partitions of a poset with one specified value

Given a poset $P$ and an element $x \in P$. How many plane partitions of height $m$ (order preserving maps from $f:P \to [1,m]$), exist when $f(x)=j, 1 \leq j \leq m$? I'm interested in this as a way ...
0
votes
1answer
294 views

Method for finding bridges and articulation points using DFS

How can we find all bridges and articulation points using DFS? Suppose we have the following DFS psuedocode (from Wikipedia): ...
1
vote
1answer
23 views

Number of vertices and edges of two isomorphic graphs

I am given the definition of graph isomorphism as follows: Let $G$ be a graph with vertex set $V_G$ and edge set $E_G$, and let $H$ be a graph with vertex set $V_H$ and edge set $E_H$. Then $G$ is ...
1
vote
1answer
36 views

Suggest books on Combinatorial Graph Theory

I am going to start self-studying Combinatorial Graph Theory. Kindly suggest books or study materials available online. I have been told that it is basically application of linear algebra, mainly ...
1
vote
1answer
29 views

On a possibility/impossibility of a certain twisted situation in a tournament

Recently I encountered the following puzzle: Consider a game for two players which can only result in a win of one of the players (no ties). Now $n$ players decided to play this game each with ...
0
votes
0answers
19 views

Count the number of functional digraphs with special restrictions

Given a set of $n$ nodes, how can I count the number of possible functional di-graphs whose biggest connected component contains k node? With a restriction that no node can have an edge point to ...
1
vote
1answer
15 views

Question about proof of Ore's Theorem

Ore's Theorem: If $G$ is a simple graph such that for every pair of non-adjacent vertices $u, v$ of $G$ we have $d(u) + d(v) ≥ |G|$, then $G$ is Hamiltonian. I am able to follow the classic proof ...
2
votes
2answers
27 views

The Greatest Number of Edges on a Bipartite Graph

Let $G$ be a bipartite graph on $p$ vertices. Find a formula in terms of $p$ that determines the greatest number of edges that $G$ could have. Prove that this formula is correct. Let $V$ be the set ...
0
votes
2answers
617 views

Cycle containing two given nodes in an undirected graph

Given an undirected graph G=(V,E) and two nodes s, t in V, how to FIND an arbitrary SIMPLE cycle (each node used only once) between s and t? Or just DETECT whether there is a cycle between them? Here ...
10
votes
1answer
2k views

Triangle dissection, no shared edges

It's possible to divide a triangle into smaller triangles such that no edge lengths are shared. Alternately, no two internal triangles share two vertices. The top three are the known simplest ...
1
vote
0answers
15 views

Fully connected subgraphs - what is it called and what is an efficient way of finding one?

By 'fully connected subgraph' I mean two (not necessarily complete) subgraphs, where each node in one is connected/mapped to each node in the other. I have not been able to find a name for this - it ...
2
votes
1answer
67 views

Sequence of Erdos-Renyi random graphs convergent with probability 1

Definitions Let $H,G$ be finite simple graphs. Then the density of $H$ in $G$, denoted $d(H,G)$, is defined as the probability that a randomly chosen $|H|$-tuple of vertices of $G$ induce a graph ...
4
votes
0answers
41 views

Is there any relationship between topological and graphical connectedness?

We have two ideas of contentedness from two different branches of mathematics - Topology and Graph Theory. One talks about the connectedness of a space and another about a graph. But does there exist ...
1
vote
1answer
16 views

A scatter graph with all vertices meeting at a common vertex

I have been wanting to find the fairest way to find a meeting place for all my n>2 clients, or vertices. The journey that each client must travel, edge length, must be so that no single client travels ...
0
votes
0answers
20 views

Which of the statements are true for travelling sales man problem of a greedy algorithm [on hold]

Which of the statements are true for travelling sales man problem of a greedy algorithm work’s for in complete graph also Krushkal’s algorithm gives a sub-optional solution in general Both $(1)$ and ...
1
vote
1answer
20 views

Matrix-Tree Theorem: proof with graph characteristic polynomial

This is a follow-up question regarding my previous one. I went through the sections: 1.1 and 1.2 of the following script. I am in the middle of the section 1.3 but I do not understand what is ...
0
votes
1answer
28 views

What is difference between $O(|V|+|E|)$ and $O(|V+E|)$?

Perform DFS over the entire graph. The linear time taken by a size of graph as visiting each node finished is put it on the head of initially empty list is $O(|V|+|E|)$ $O(|V+E|)$ $O(|V|^k)$ $O(\...
2
votes
0answers
50 views

Biggest Unsolved Problems In Graph Theory ( a la Riemann Hypothesis to Number Theory)

I'm not sure whether this is the right place for this question, but what are the most major unsolved problems in graph theory? (Not just a list, but something like a top 10 list or something like that)...
5
votes
1answer
124 views

Minimum number of edges such that $\chi_1=\chi$ (version 2)

I have asked this question a few months ago here. I received an answer that I will explain, but found a mistake in the proof. I am looking for new answers, or for a way to correct the one that has ...
0
votes
0answers
19 views

What are some of the existing methods (preferably with implementations) that cluster dynamic brain network data with signed edge weights? [closed]

I have a dynamic graph data with nodes and edges attributed to each timestep. The problem is to find how many communities are found at each timestep and what is their membership. I have an existing ...
1
vote
0answers
26 views

Is there a non-trivial special orthogonal transform which preserves the diagonal elements of a symmetric matrix with positive entries?

This problem is at the interface of matrix algebra and spectral graph theory. Let $\mathbf{S}$ be a symmetric $n\times n$ matrix, with positive entries $S_{ij}\geq 0$, and $\mathbf{D} = \mathrm{diag}(...
2
votes
1answer
16 views

Finding a special sequence of colors in an edge-colored graph

Say I am giving a directed edge-colored graph $G^c(V,E)$. Every vertex has the same out-degree. Every vertex has exactly one edge of one color in $I_c$. So for example, if you have a set of color $I_c ...
1
vote
0answers
20 views

maximum number of edges given diameter and number of vertices [closed]

Let us assume that $G = (V,E)$ is an undirected unweighted simple graph. Let $d$ is the diameter of the graph $G$, $n$ is the number of vertices, and $m$ is the number of edges. Now I am looking for ...
2
votes
1answer
32 views

All directed paths between any two vertices have the same length

Is there a term for the condition that, given some directed graph $G = (V, E)$, for all $v, w \in V$ every directed path from $v$ to $w$ has the same length as every other?
1
vote
0answers
42 views

Given N blocks, find the number of unique shapes in a NxN block

Constraints: The blocks must be adjacent to each other. i.e. A pair of blocks must have a common edge or vertex. Any shapes that are formed by flipping or rotating or mirroring should be considered to ...
11
votes
2answers
5k views

Proof : cannot draw this figure without lifting the pen

This question maybe ridiculous but I always found it interesting... Here it is : (I cannot put image so I put you the link of the pictures) When I was in school I used to draw houses when I was bored :...
3
votes
2answers
462 views

Draw this shape - no double lines, no lifting pen? Impossible!?

I'm 99% sure this isn't possible! But... is there anyway to draw this shape without lifing the pen and without redrawing over any lines?! Thanks :-)
0
votes
1answer
12 views

Tournaments with no round trips

Let $T = (V,E)$ be a tournament with no round trips (by which I mean a sequence $v_0, \ldots, v_{k+1}$ of vertices such that for $i<k+1$ we have $(v_i,v_{i+1})\in E$ and $v_0 = v_{k+1}$, for some $...
0
votes
0answers
9 views

Turan number for disjoint union of complete graphs

I have been trying to locate literature relating to the Turan number for disjoint union of complete graphs, i.e. $ex(n, tK_r)$, where $K_r$ is the complete graph. My search has so far been ...
7
votes
8answers
12k views

Why does a complete binary tree of $n$ leaves have $2n-1$ nodes?

A complete binary tree is defined as a tree where each node has either $2$ or $0$ children. A variety of sources have described the relation between nodes and leaves to be $2n-1$ where $n$ is the ...
2
votes
1answer
63 views

Chromatic number of graph of subsets of a set [closed]

Suppose set $A$ with $2n$ elements. Construct simple graph $G$ with $\left(\begin{array}{c}2n\\ n\end{array}\right)$ vertices each one represents one of $n$_sized subsets of $A$ .Connect any two ...
2
votes
2answers
47 views

Find least number of radial-subgraph of a graph

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader? ...
-1
votes
0answers
12 views

Construction of Planar Graph W/ Even-Degree Faces [closed]

Is there an "algorithm" for construction a planar graph with any number of even-degree (degree >=4 faces?
1
vote
1answer
111 views

Minimum cost path with variable costs and fixed number of steps

I'm facing with the following problem. Suppose to have a generic oriented graph with curl (there can be an edge from a node to itself). Suppose also that you have to perform a $n$-vertices-long ...
1
vote
1answer
47 views

Degree $d$ non-isomorphic graph count [closed]

How many non-isomorphic regular graphs are there are $n$-vertices with degree $d$?
2
votes
0answers
27 views

Probabilities maximizing a graph's “guaranteed yield”

It is given a finite directed graph with $v\ge2$ vertices $V_i$, such that for all indexes $i$ and $j$ (with, implicitly, $0\le i<v$ and $0\le j<v$) there exists at most one directed edge from ...
3
votes
4answers
324 views

Computing a sum of binomial coefficients: $\sum_{i=0}^m \binom{N-i}{m-i}$

Does anyone know a better expression than the current one for this sum? $$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$ It would help me compute a lot of things and make equations a ...
2
votes
0answers
47 views

Provable Hamiltonian Subclass of Barnette Graphs

Given a bicubic planar graph consisting of faces with degree $4$ and $6$, so called Barnette graphs. We can show that there are exactly six squares. Kundor and I found six types of arrangements of the ...
1
vote
1answer
24 views

Why study graph representations of equivalence relations?

What is the importance of representing a (an equivalence) relation using digraphs? Is there any geometric aspect to study relations using graphs (of vertices and edges)?
3
votes
2answers
968 views

Belt Balancer problem (Factorio)

So this question is inspired by the following thread: https://forums.factorio.com/viewtopic.php?f=5&t=25008 In it, the poster is examining an $8$-belt balancer (more on that to come) which he ...
3
votes
1answer
65 views

proof of Triangle Removal Lemma

Where can I find a proof of the following version of Triangle Removal Lemma (or any version equal to it)? Let $G(V,E)$ be a graph on $n$ vertices such that it contains $\varepsilon n^3$ triangles, ...
2
votes
1answer
36 views

Can someone explain this proof of the relationship between chromatic number and independence number to me?

I came across the following claim and proof in this paper, and I really don't follow. If $G$ is a vertex-transitive graph with independence number $\alpha$ and chromatic number $\chi$ then $n/α(G) ≤...
-4
votes
0answers
18 views

About bandwidth! o(1) problem [closed]

Title: On the Bandwidth of a Random Graph Authors: Kuang and McDiarmid Theorem: Let 0 I know that the bandwidth of Petersen graph n=3, k=1 is 3. I want to check if Kuang's theorem holds for this ...
1
vote
1answer
48 views

Is there a general strategy for identifying the automorphism group of a graph?

I understand what an automorphism is, and I can sort of wrap my head around the idea that the set of automorphisms under composition form a group, but when asked to actually find the automorphism ...