# 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.

9 views

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

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

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