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
0answers
14 views

Tree of arity n: How to call a vertex that has only k (k<n) children?

What is the correct adjective for a vertex in an n-ary tree that has only k children (k < n)? I was thinking of something like "unsaturated", but I don't know if that is the correct word for this. ...
0
votes
0answers
19 views

Number of Strongly Connected Components and Property Testing.

I am working on a problem about the strong connectivity of digraphs. Given graph $\vec G$ that is $k$-$\textit far$ away from being strongly connected (i.e, the minimum number of edges that need to be ...
0
votes
0answers
14 views

Interpolating graph path

I have a directed graph with very few nodes, and I would like to add many more redundant nodes between them. So if I have A->B->C, I'd like to get A->A0->A1->A2->B->B0->B1-B2->C The intermediate ...
0
votes
0answers
51 views

Is this composition of $K_{4,4}$ graphs minor-closed?

Following graph is a composition of $K_{4,4}$ bipartite graphs with all the edges are of same length. How do I know whether it is minor-closed or not? The definition in the Wikipedia is as follows. ...
0
votes
0answers
20 views

Let $g$ be a matrix corresponding to a directed graph so that $g_{ij}$ is the edge weight on an edge $ij$. How can we interpret $g^k$?

I know that if $A$ is a 0-1 adjacency matrix then $[A^k]_{ij}$ is the number of walks of length $k$ from $i$ to $j$. Does this generalize nicely? The reason for this question is to interpret a result ...
0
votes
0answers
34 views

Relation between girth and lower bound of the number of vertices

Let $G$ be a graph with girth $g > 3$. Suppose that every vertex in $G$ has degree at least $k > 1$. Can we found a nice lower bound for $|V(G)|$? Let me be more specific on what I want: ...
0
votes
0answers
37 views

Number of unique ways to edge-label a complete graph with $k$ distinct labels.

Given $k$ distinct labels, how many unique ways to label the edges of a complete graph with $n$ nodes (nodes are not labeled). For example, to label a complete graph with 3 nodes using 4 distinct ...
0
votes
0answers
24 views

example of algebraic theory,free product completion,graphs

Let us denote by $\def\Graph{{\sf Graph}}\Graph$ the category of directed graphs $G$ with multiple edges: they are given by a set $G_v$ of vertices, a set $G_e$ of edges, and two functions from $G_e$ ...
0
votes
0answers
31 views

maximum k-colorable subgraph

Problem: Given an arbitrary graph $G$ and $k$ colors, find a maximum $k$-colorable sub-graph of $G$. Question: This problem is known to be NP-complete. Is there any solution to this problem, whatever ...
0
votes
0answers
32 views

I need several definitions from Graph Theory corrected.

Definitions below might sound awkward because I wrote them down in my own words. Please, see if any of that needs fixing. $V(H)$ is the set of all vertices of the graph $H$. $E(H)$ is the set of all ...
0
votes
0answers
47 views

Miscellaneous questions about trees

I want to know which of the following claims are true: 1) Let T be a minimal spanning tree in G for a weight function w. Then T is also a minimal spanning tree for the weight function obtained from w ...
0
votes
0answers
12 views

(Alternative) Notation for set of successors of a vertex in a directed graph

I am looking for the standard notation for the set of successors/predecessors of a vertex of a directed graph. I have seen $N^{+}(v)$ and $N^{-}(v)$ used to represent the set of direct successors and ...
0
votes
0answers
19 views

Q: Finding probability of connection based on distance?

So, I am new to graph theory and statistics but have encountered a problem that I am not exactly sure how to solve. I have a graph with n nodes and am trying to determine the probability of connection ...
0
votes
0answers
18 views

Resizing Edge Weights Bases on Node Sizes

I am new to graph theory and I and trying to create edge weights based on the sizes of the connecting nodes. My problem in particular is as such: I have a directed graph of e-mails that were sent ...
0
votes
0answers
15 views

Can Wiener process on a fractal random graph be reduced to a levy flight?

Weiner process on small-world graphs is a Levy flight. But does the condition still hold for a random graph that connects the edges of a fractal?
0
votes
0answers
65 views

Find the flaw in my 1-page proof of the Four Color Theorem

The Four Color Theorem has been proven for quite a while now, so I'm not really breaking ground there. But last night, for some reason, it popped into my head and I started thinking about it. I feel I ...
0
votes
0answers
34 views

Signing the attendance

Imagine N students sitting in a straight row, students are numbered 1 to N. Attendance sheet is first given to student 1, who uses his own pen to sign the sheet. Then he passes the sheet to student 2, ...
0
votes
0answers
22 views

Matrix norm to compare two graphs

I have the adjacency matrices of two undirected graphs. I want to measure how different the two matrices are in terms of the linkage. Both matrices have the same number of nodes, but they differ in ...
0
votes
0answers
43 views

Face Boundary and bipartite question classification

Is this question wrong? Let G be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that G is bipartite. Consider a graph of 2 squares ...
0
votes
0answers
23 views

What is the edge called that converts a tree to a directed acyclic graph?

Neither Wikipedia nor mathworld gave the answer: What is the name of the edge (or multiple edges) without which a DAG would be a tree? Or maybe instead: What is the name of the subgraph such that ...
0
votes
0answers
38 views

Min. Spanning Tree - Same weight

Prove that every minimum spanning tree of a connected graph, $G$, has the same maximum edge. Intuitively, this makes sense to me. You need to have that heavy edge because that is the cheapest ...
0
votes
0answers
38 views

How to reduce a graph via decomposition?

Is there a Java / C# library that can be used to reduce a graph via decomposition? Or could someone point me to a good tutorial where I can learn all these? E.g.
0
votes
0answers
27 views

Hypergraph notation and hypergraph morphisms

There are two parts to my question. The first part is about notation for hypergraphs. The sconed is about the notion of morphisms for hypergraphs. For the notation part, the context is that I make ...
0
votes
0answers
10 views

Poisson distributed graphs

I am currently reading a paper about poisson distributed graphs and came across the following formula. Apparently the degrees of the graph are distributed binomially through the following ...
0
votes
0answers
22 views

Threshold function for component of size $k$

Show that, for each fixed $k$, there is a function $p(n)$ such that the probability that $G(n,p(n))$ has a component of size exactly $k$ tends to $1$ as $n \rightarrow \infty$. My initial thoughts are ...
0
votes
0answers
42 views

How to show a total order is product order

Besides the definition of product order, is there any other way to show that a total order on two sets can induce a product order? Because I want to solve the problem below: For two graphs ...
0
votes
0answers
58 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
0
votes
0answers
36 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
0
votes
0answers
19 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
0
votes
0answers
10 views

Average time to split a square lattice under random edge deletions

Suppose one successively deletes uniform at random edges from the square lattice with periodic boundary conditions and $L\times L$ sites. How many steps, in average, are necessary to create a second ...
0
votes
0answers
34 views

A planar graph has either 2 faces or 2 vertices of degree less than 3

Practicing for an upcoming test, I stumbled upon this question: A planar graph with at least three vertices has either 2 faces of length at most 3, or 2 vertices of degree at most 3. Which is a ...
0
votes
0answers
50 views

Smart Travelling Agent Problem

Smart travel agent, Mr. X's is to show a group of tourists a distant city. As in all countries, certain pairs of cities are connected by two-way roads. Each pair of neighboring cities has a bus ...
0
votes
0answers
39 views

What is exactly a DFS tree?

Here's a question: Claim: Every time we run the DFS algorithm on the following graph, The DFS tree will be lanyard (?) True \ False, Explanation: I Googled but I'm not pretty ...
0
votes
0answers
18 views

Induction over DAGs

I'd like to prove a proposition true over all valid Directed Acausal Graphs. I think I can do that by starting with a graph with one node and adding either a new node and connection, or a new valid ...
0
votes
0answers
13 views

compare magnitude of elements of Perron-Frobenious vector

Consider a nonnegative, primitive matrix $A=(a_{ij})_{n\times n}$ with positive diagonals. From the Perron-Frobenious theorem, the spectral radius $\rho(A)$ is an eigenvalue of $A$ and we have a ...
0
votes
0answers
34 views

Percolation Theory Basics: Open cluster size decay (Square Lattice)

I am trying to learn some stuff about percolation. On wiki (http://en.wikipedia.org/wiki/Percolation_theory) it says: "when $p<p_{c}$, the probability that a specific point (for example, the ...
0
votes
0answers
29 views

Graph theory problem of directed graph

Given a directed graph how can one find whether there exists a path that has all the vertices connected in short how can one know whether there exists a spanning tree in a directed graph or not. ...
0
votes
0answers
18 views

Cactus construction

Is there someone who can explain me how can one construct the cactus of the minimum cuts of a graph? Or someone who can suggest me a book about cactus construction theory? Thank you in advance
0
votes
0answers
24 views

Algorithm to check if a graph has exactly one perfect matching

What is an algorithm to check if a general graph has exactly 1 perfect matching? Or an algorithm to check whether a graph has more than 1 perfect matching?
0
votes
0answers
22 views

the size of every dominating set for a random graph $G(n,p)$ which at least every vertex has degree $\frac{n}{2}$ is at least $\Omega(\log(n))$..

the size of every dominating set for a random graph $G(n,p)$ which at least every vertex has degree $\frac{n}{2}$ is at least $\Omega(\log(n))$. I tried a lot to solve this one,but this doesn't seem ...
0
votes
0answers
28 views

Min cuts of a graph with odd edge-connectivity

Let $G=(V,E,w)$ be a weighted graph with integer weights, odd edge-connectivity $k(G)$ and $|E|$ minimum cuts that are linearly independent (i.e. every edge is contained in a minimum cut). Is it true ...
0
votes
0answers
36 views

How to calculate least moves of fruit.

I have a question, I'll try to abstract from the real problem to not lose people. What I'm really looking for is the name of the algorithm or class of problem to find my solution. I feel that this is ...
0
votes
0answers
52 views

How many trees, not necessarily spanning, are there with exactly m edges and n vertices?

I've been struggling with this combinatorical question and got very confused: Given $n$ vertices: $\{v_1,v_2,\ldots,v_n\}$, in how many ways can a tree be assembled upon them, not necessarily ...
0
votes
0answers
39 views

Check if there's a cycle in an undirected graph

I'm trying to find an algorithms that checks if there's a cycle in a given undirected graph G=(V,E). But I didn't succeed. Can anyone give me such an algorithm?
0
votes
0answers
7 views

The $k$-core of a random geometric graph

I have not been able to find a lot of literature on the $k$-core of a random geometric graph and i was wondering if anyone knew of any results?
0
votes
0answers
44 views

$k$-coloring problem which minimizes the number of conflicting vertices

Classical $k$-coloring problem (k-GCP) is to assign a color selected from $k$ colors to each vertex of graph $G$ so that the number of conflicting edges (the edges with same color endpoints) is ...
0
votes
0answers
44 views

Calculating Eigenvector Centrality & Betweenness Centrality formulas explained in simple terms

I'm currently working on a software application that has a function that analyses networks of people and the relationships between them. Two of the important variables we look at are Eigenvector ...
0
votes
0answers
25 views

Prove a problem about Networks(in graph theory)

$S$ and $T$ are two subsets of $V(N)$, which is the set of vertices in network N. Let $S^c$ denotes the complement of $S$ and $[S,S^c]$ be the set of arcs starting in $S$ and finishing in $S^c$. If ...
0
votes
0answers
11 views

Appearance of small subgraphs

I had a quick question regarding top of page 16 in the '9 lectures in random graphs' http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf It says there are $O(n^{2v-j})$ choices of ...
0
votes
0answers
51 views

Is there a specific name to this graph?

The other day I was asked about the name of a given graph someone was drawing... It looks like a cobweb graph, but it doesn't have a hole in the center. In fact, it is just like a wheel graph with ...