Tagged Questions

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.

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 ...
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 ...
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,...
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\}$?
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 ...
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 ...
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 ...
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): ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
28 views

16 views

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 ...
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 ...
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 ...
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? ...
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?
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 ...
47 views

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

How many non-isomorphic regular graphs are there are $n$-vertices with degree $d$?
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 ...
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 ...
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 ...
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)?
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 ...
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, ...
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) ≤...