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
34 views

Cut Space of Vertices without Orthogonal Complement of Cycle Space?

I am studying sparse graphs where their complements tend to be dense (not sparse). I understand this so that the sparse graph has a sparse adjacency matrix while its graph complement is not most ...
0
votes
0answers
10 views

Chromatic number of famous lattices

What are the chromatic numbers of some well-known lattices, e.g. $E_8$ lattice, Leech lattice? (Here, of course the chromatic number means the chromatic number of the tangency graph of a lattice.)
2
votes
0answers
21 views

Show that matrix is totally unimodular

I want to show that this matrix is totally unimodular: \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & ...
1
vote
1answer
22 views

Which of the following is NOT true for $G$?

$G$ is a graph on $n$ vertices and $2n−2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$? For every subset of $k$ ...
1
vote
1answer
40 views

How does $\frac{1}{2}(n-s+1)(n-s)$ equal $\binom{n-s+1}{2}$?

Maybe a basic question, but I'm strolling through graph theory at the moment after a few years out of tertiary mathematics. There is a theorem that if a graph $G$ has $s$ connected components, then $$ ...
1
vote
0answers
23 views

Conditions for friendship paradox variant

The friendship paradox is sometimes summarised as stating that: Most people have fewer friends than most of their friends. However, the mathematical explanation provided usually shows something ...
2
votes
1answer
15 views

Why $\left\lceil{ \frac{n}{1 +\Delta (G)}}\right\rceil \ge \gamma (G)$?

a dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in$ D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in ...
1
vote
2answers
29 views

Chromatic number of a graph

Construct a graph $G$ as follows: The vertices of $G$ are the edges of a complete graph $K_5$ on 5 vertices. The vertices of G are adjacent if and only if the corresponding edges of $K_5$ have an ...
0
votes
1answer
21 views

Finding a counterexample for two conditions about graphs

I have the following algorithms for DAGs: Minimum path cover counter, which returns the least number of paths which cover the vertices. The following algorithm: count the vertices with in degree = ...
0
votes
0answers
40 views

How many Fano Planes Can We Build with the Numbers from $1$ to $35$

The Fano plane is the finite projective plane of order 2, having the smallest possible number of points and lines, 7 each, with 3 points on every line and 3 lines through every point. Assume that ...
1
vote
1answer
24 views

Topological Notation of a Dynamic Probabilistic Graph

I am trying to figure out how to formally describe a probabilistic directed graph. In plain English the properties of the graph are as follows : A graph is comprised of a set of nodes each with 2 ...
0
votes
0answers
17 views

Edge Chromatic Number of Product Graphs

Assume that two graphs like $G$ and $H$ are given. $G \times H$ is a graph such that every vertex of it comes from $V(G) \times V(H)$ and every vertex like $(u,v)$ is adjacent to $(u',v')$ iff : ...
1
vote
1answer
25 views

An algorithm for proper edge-coloring of every simple graph with $\delta+1$ colors

A proper $k$-edge-coloring for a graph like $G$ is coloring every $e \in E(G)$ with $k$ colors such that no two edges of the same color share a common vertex. According to Vizing Theorem, for every ...
0
votes
0answers
11 views

Why is a “scale-free” network defined as one whose degree distribution obeys a power law?

Aren't these two different concepts? I think "scale-free" refers to the fact that the degree distribution doesn't depend on the size of the network. So wouldn't a network with degree distribution ...
1
vote
0answers
54 views

Number of different minimal proper edge colorings of $K_n$

How many minimal proper edge colorings of $K_n$ are there? A minimal proper edge coloring of a complete graph is a coloring of $K_{2n}$ with $2n-1$ colors or $K_{2n-1}$ with $2n-1$ colors are there ...
2
votes
0answers
198 views

Sifting Technique : Construction of Isomorphism from sets of Local Isomorphism(Graph Isomorphism)

Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume $H$ has subgraphs $H_1, H_2... H_x$ (total $x$ vertex set). ...
0
votes
0answers
6 views

How does flow of probabilistic influence differ between directed and undirected graphs?

I was reading up on probabilistic graphical theory and it's not very clear how the flow of probabilistic influence differs between directed and undirected graph. My initial assumption was that flow is ...
31
votes
5answers
713 views

A disease spreading through a triangular population

I have run into this problem in my research, which I'm presenting under a different guise to avoid going into unnecessary background. Consider a population that is connected in a triangular manner, ...
1
vote
2answers
159 views

If $\Delta(H)\leq 3$ and $H$ is a minor of $G$, then $H$ is a topological minor of $G$.

If $\Delta(H)\leq 3$ and $H$ is a minor of $G$, then $H$ is a topological minor of $G$. The converse follows by definition. However, most sources state this proposition without a proof. Any help is ...
2
votes
1answer
95 views

Total number of edges in a triangle mesh with $n$ vertices

Given a 2D triangle mesh with $n$ vertices, I was wondering if there is an expression that would allow to compute the total number of edges present in the mesh. For example, the following mesh has 6 ...
5
votes
2answers
209 views

{0,1}-matrix and permutation matrices

A permutation matrix is a square matrix with exactly one $\textbf{1}$ in each row and column, and zeros in all other positions of the matrix. Let $M$ be an $n\times n$ $\{0,1\}$ matrix with exactly ...
4
votes
2answers
39 views

Must the number of people…

Must the number of people at the party who do not know an odd number of people be even? Describe a graph model and then answers the question. I'm confused because I do not understand the ...
0
votes
1answer
11 views

Build a 4-regular, vertex-transitive, least diameter graph with v vertices

How to build a 4-regular, vertex-transitive, 'least diameter' graph with $v$ vertices? This implies to know what is the minimum diameter of a 4-regular vertex-transitive graph with $v$ vertices. ...
2
votes
2answers
59 views

Give a graph model for a permutation problem

Describe a graph model for solving the following problem: Can the permutations of $\{1,2,\ldots,n\}$ be arranged in a sequence so that the adjacent permutations $$p:p_1,\ldots,p_n \text{ and } ...
-3
votes
1answer
41 views

How do I construct a 5 regular maximal planar graph? [closed]

Well to start off, $5n=2e$ since there will be $n$ number of vertices of degree 5 and with the handshaking lemma, there will be $2e$. The problem is finding the number of vertices and faces. What do ...
0
votes
1answer
26 views

How to find the number of faces of a rhombicosadodecahedron?

I need to use the Euler's formula. I know there are $62$ faces...first, how do I find the number of vertices it has. From there, I can get the amount of edges, which will then in turn get me the ...
30
votes
0answers
457 views

What is that thing that keeps showing in papers on different fields?

A few months ago, when I was studying strategies for the evaluation of functional programs, I found that the optimal algorithm uses something called Interaction Combinators, a graph system based on a ...
1
vote
0answers
17 views

Is there nessary condition for which a graph $G$ has a homomorphism but no surjective homomorphism to $H$?

Is there (sufficient and) nessary condition for which a graph $G$ has a homomorphism but no surjective homomorphism to $H$? Where the surjective means both vertex and edge are surjective. Or say if ...
2
votes
0answers
31 views

What measures of centrality exist for fully connected networks with weighted directed edges?

I have a network of cities with transport links between them. The transport links are not symmetric in both directions, therefore asymmetric edges between nodes. There is a variable number quantifying ...
4
votes
1answer
571 views

Definition of Tensor Product of Graphs

Let $G$ and $H$ be graphs, then connect two elements $(g, h)$ and $(g', h')$ of $G\times H$ if and only if $gg'\in G$ and $hh' \in H$. Does the tensor product of graphs have to do with the tensor ...
0
votes
0answers
25 views

Discretizations of Differential, Geometric and Topological Notions

I have noticed a recurring theme in Graph Theory / Theoretical Computer Science (abbreviated GT and TCS throughout this post) in that notions typically belonging to differential calculus / geometry / ...
0
votes
1answer
31 views

Connected Linear Graph not Path-Connected

Given a set of vertices $\{x_\alpha\}$ whose cardinality exceeds $\aleph_1$, (assume the axiom of choice) connect each vertex with its successor by an edge, forming a linear graph. Choose two vertices ...
0
votes
1answer
24 views

In Graph to tree: name of operation where edges removed and vertex/edge additions?

The graph has tree paths IN-1-OUT, IN-2-OUT and IN-3&4-OUT between IN and OUT in the left. I want to make each path to a branch like the right. What is the name of this operation or the name ...
0
votes
0answers
36 views

What is an intuitive way to understand Cayley's formula?

Is there any intuition behind Cayley's formula $n^{n-2}$ for the number of spanning trees of a graph?
0
votes
1answer
19 views

Partially ordering finite graphs

What are some interesting partial orders on the set of all finite graphs (identified up to isomorphism), apart from the usual (induced) subgraph relation and the (topological) minor relation, and why ...
-2
votes
0answers
18 views

Hamiltonian cycle problem_

Show that, if a graph with n vertices has at least $\frac{(n-1)(n-2)}{2}+2$ lines than it's a Hamiltonian cycle. How can I solve this problem?
0
votes
1answer
28 views

Properties of non-trivial automorphism

I am reading Sanjeev Arora and Barak Boaz. I am stuck at proving the following which the book assumes to be trivial result. Following are the point I am stuck at If we are given a graph $G$ ( with ...
1
vote
1answer
26 views

How many surfaces have $4$ edges…

A 3 regular, plane, connected graph have all surfaces either $4$ or $6$ edges (including the outer surface). How many surfaces has $4$ edges? Let $x$ be the number of surfaces that have $4$ edges ...
0
votes
0answers
16 views

Relation between Kolmogorov Zero-One Law and Random Graphs Zero-One Laws?

I know of Zero One laws for Random graphs (such as those concerning monotonic or first-order-logic properties). I also know about Kolmogorov's zero one law for tail sigma algebras. Apart from the ...
1
vote
1answer
46 views

How to generate (recursively?) all non-isomorphic trees with 2 types of vertex labels with degree restrictions?

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following: 1) Each vertex (including leaves) has one of two labels ...
0
votes
0answers
45 views

Number of connected graphs with multi edges

Given $n$ distinct nodes $1,2...n$, I wish to find the number of connected graphs with these $n$ nodes. I have seen the previous question : How to calculate the number of possible connected simple ...
-1
votes
0answers
27 views

Is this graph is DFS or BFS?

Is is this graph is depth first search spanning tree or breadth first search spanning tree
0
votes
1answer
26 views

Graph theory 27 cube cheese and mouse problem [duplicate]

A cubic cheese consists of 27 smaller cubes of cheeses (3x3x3). A mouse will eat the first cheese cube and then eat an adjacent cheese cube (no diagonal eating allowed). Show that the mouse can't end ...
1
vote
1answer
1k views

Dijkstra's Algorithm on a Directed Graph with Negative Edges Only Leaving the Source

I've been trying to figure out if Dijkstra's algorithm will always succeed on a directed graph that can have edges with negative weights leaving the source vertex only (all other edges are positive), ...
1
vote
1answer
35 views

Is there a graph with $n$ vertices and $n^2/4$ edges that isn't bipartite? [closed]

Is there a graph with $n$ vertices and $\lfloor n^2/4\rfloor$ edges that isn't bipartite and contains no triangles ($K_3$)? Rather, what I am asking is whether Mantel's Theorem implies that every ...
0
votes
0answers
70 views

100 people standing in a circle.

I've got this problem on my Graph algorithms exam and I still can't solve it!Here is the problem: At first there are 100 people sitting at a round table and neither one is enemies with their ...
0
votes
0answers
17 views

Algorithm to Find Highest Path in a Directed Acyclic Graph

Let $G=(V,E)$ be a directed acyclic graph. We will define the function $h:V\rightarrow R^+$, where h(v) is the height of v. Let $P=(v_1,...,v_k)$ be a path. We will also define ...
0
votes
1answer
29 views

Show there is a subgraph of G with minimum degree k

Let $G$ be a simple, connected graph with $n\ge k+1$ vertices and $m\ge (k-1)(n-k-1)+{k+1 \choose 2}$ edges. Show there is a subgraph of $G$ with minimum degree at least $k$. (Not necessarily ...
0
votes
0answers
14 views

Show there are 2 distinct paths that connect two foreign subsets of a 2-connected graph

Let $G$ be a simple 2-connected graph with at least 4 vertices. If $V(G)$ the set of vertices, let $U,W$ be subsets of $V$, with no common elements, with $|U|=|W|=2$. Show that there are 2 distinct ...
1
vote
0answers
34 views

Any good “Ted Talk” sources for appreciating graph theory? (Vague/vogue question alert)

I would like to learn more about Graph Theory. Just a "Ted Talk" caliber understanding. I've played with Bridges of K. and 4-color map. I get that stuff like Facebook or Netflix movie reviews may ...