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

2
votes
1answer
9 views

If set $A_n$ converges to $A$ in $L^1$, then is it also true for the $r$-neighborhood?

Let $A$ be a bounded simply connected set in $\mathbb{R}^2$, and $A^r$ denote the $r$-neighborhood of $A$, that is, $A^r:=\{x: d(x,A) \le r\}$. Suppose there exists $A_n \rightarrow A$ in $L^1$ and $d(...
3
votes
3answers
20 views

Prove that all trees are bipartite

I've been trying to prove this for a while. I can think about it intuitively, but I can't come up with a formal proof. I would appreciate some help. Here's how I'm thinking about it Let T be the ...
1
vote
1answer
6 views

Spanning 2-regular subgraphs in even regular graphs.

Theorem: Every regular graph of positive even degree has a spanning 2-regular subgraph. This was taken from Corollary 5.10 of ETH Zurich's notes on graph theory. The proof constructs a Eulerian tour,...
1
vote
0answers
26 views

Elementary proof for average number of tree components in a random forest of fixed size

In Flajolet's & Sedgewick's "Analytic Combinatorics" I found the statement that for a forest ("Catalan", i.e. collection of ordered trees) of size $n$, uniformly distributed, the number of tree ...
1
vote
1answer
16 views

Combinatorial problem on finding the index associated to an edge of a complete graph

Ok so here is a combinatorial problem that I thought of. Suppose N is in $\mathbb N$ such that $N>1$, then there is a way to count (set an index) to all pairs $(i,j) \in \{1,\dots,\mathbb N\}\...
0
votes
1answer
45 views

rooted labeled trees with root degree 2

A colleague of mine (who is not a mathematician at all) asks me to have a look at his formula for the number $T_n$ of rooted labeled trees on $n$ vertices where the root has degree 2. He starts out ...
4
votes
0answers
25 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
20 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
43 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
0answers
17 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
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 ...
0
votes
1answer
32 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 ...
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
30 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 ...
1
vote
1answer
18 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
30 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 ...
1
vote
1answer
24 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
0answers
16 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 ...
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
21 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
51 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)...
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
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
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 ...
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 ...
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 ...
-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?
2
votes
0answers
28 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 ...
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
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
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 ...
1
vote
1answer
25 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)?
-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 ...
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 ...
2
votes
2answers
48 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? ...
0
votes
0answers
26 views

Graph with small automorphism and large isomorphism

Is there a graph family on $n$-vertices such that any graph $G$ in the family have small automorphism group (say $|Aut(G)|\leq n^c$ for some fixed $c>0$) which if $G$ and $H$ are isomorphic then ...
2
votes
0answers
98 views

Number of ways to connect vertices of n squares with line segments

What is the number of ways to connect the vertices of n squares with non-intersecting line segments ? These line segments should not cross the edges of the given squares as well. Obviously $N(3)$ is ...
1
vote
1answer
50 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 ...
0
votes
2answers
14 views

Is there always a minimal coloring for a graph for which one of the colors is a maximum set?

Take a graph $G$ and suppose it is $k$-chromatic. Is there always a $k$-coloring such that one of the "colors" (the independent sets that compose the coloring) will have cardinality equal to $G$'s ...
2
votes
1answer
37 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) ≤...
0
votes
0answers
34 views

Non-isomorphic graphs with trivial automorphism group

Given $n$ as number of vertices is it possible to find $n^c$ non-isomorphic graphs each with a trivial automorphism group for some fixed $c>1$ in deterministic polynomial time? It is easy to find ...
0
votes
1answer
45 views

Matrix-Tree Theorem for rooted directed graphs

I am working my way through the proof of the theorem on the pages: 3,4,5 in the script here. I understand almost everything but the most essential idea: how to connect ...
0
votes
1answer
54 views

Calculating the average time in each node when 'hopping' through a graph

I'm dealing with a graph that looks like this: The nodes are numbers from 0 to 9, and the vertices are bi-directional. Starting from node 0, a figure 'hops' to one of other nodes connected to it, ...
5
votes
0answers
37 views

Do the two order-4 Latin square graphs have the same number of Hamilton cycles?

A Latin square graph of a Latin square $L=(L_{ij})$ of order $n$ has $n^2$ vertices $(i,j)$ and edges between distinct vertices $(i,j)$ and $(i',j')$ whenever (a) $i=i'$, (b) $j=j'$, or (c) $L_{ij}=L_{...
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 ...