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

probability in graphs - degree distribution

I am reading this paper on networks which employs probability in analyzing graphs. Suppose that a graph has $n$ vertices. Furthermore, if each vertex has a probability $p_k$ of having $k$ neighbors, ...
0
votes
0answers
12 views

Find all vertices in a DAG with the property that none lie on any path with K edges and sum of weights ≥ Threshold

Given a DAG G with weights on the edges, all nodes have a blue color. We seek to color with red every path nodes with K edges such that the sum of weights of this path is greater than a threshold (T). ...
0
votes
0answers
35 views

Diameter and maximal independent sets

I've proved that every nontrivial tree has at least two maximal indepndent sets, with equality only for stars via the bipartition of the trees. I am trying to extend that proof to general graphs, and ...
0
votes
0answers
17 views

Undirected graphs and possible vertex relationships

Given an undirected graph with visible vertices but hidden edges, and with rules such as: node A connects with at least 2 other nodes node B connects with at least 1 other node node C connects with ...
0
votes
0answers
31 views

Graph algebra papers

The following graph multiplication appears to be quite natural: Let $g_1=(V_1,E_1)$ and $g_2=(V_2,E_2)$ be two graphs ($V_i$ are sets of vertexes and $E_i$, sets of edges). Intuitively, the product I ...
0
votes
0answers
29 views

Let G be a graph on 10 vertices of degrees 1,1,2,3,3,3,4,4,5,8. How many paths of length 2 does G contain?

Let G be a graph on 10 vertices of degrees 1,1,2,3,3,3,4,4,5,8. How many paths of length 2 does G contain? Note: path of length 2 means of the form a-X-b, where a and b do not have to be distinct ...
0
votes
0answers
40 views

Expected number of steps in a random graph walk

Suppose I have a directed graph $D(V, A)$ where the edges have weights on them. Let's notate the weight function $w: A \rightarrow [0, 1]$. If $f, t \in V$ and $a \in A$ such that $a = (f, t)$ then ...
0
votes
0answers
41 views

Find a subset of edges that lie on a simple path between two vertices

I am attempting to implement an algorithm found in a paper. One of the subtasks is: "given a directed acyclic graph $(V,E)$, subset of edges $E' \in E$, and vertices $u,v \in V$, find all edges $e \in ...
0
votes
0answers
55 views

Graph with degree at least >= n/2, how adding one more edge makes it Maximal non Hamilton graph(Dirac's theorem proof for Hamilton graph)

Consider the following part of proof for Dirac's theorem: Theorem (Dirac’s Theorem 1952) If G is a simple graph with n vertices where n>=3 and d(v)>=n/2 for every vertex v of G, then G is ...
0
votes
0answers
26 views

Eigen vectors of graph laplacians

I have been reading about spectral graph theory from Daniel A. Spielman's notes. Fiedler’s Nodal Domain Theorem from this note says that : Let $G = (V, E, w)$ be a weighted connected graph, and let ...
0
votes
0answers
36 views

Graph theory matching question.

There are $n$ children and $n$ toys in a room. Each child wants to play with $r$ specific toys and for each toy, there are $r$ children who want to play with that toy. Prove that we can organize $r$ ...
0
votes
0answers
19 views

Detect Regions Described By Lines in Rectangular Coordinates

Need some help from the superior math minds here. This problem is part of a software project. Essentially, I have a Cartesian grid. The user can create lines by plotting points (every 2 points ...
0
votes
0answers
21 views

Partition of the node set of a graph into connected subsets

What word is most commonly used in graph theory for a partition of the node set of an undirected graph into connected subsets? More rigorously: Given an undirected graph $(V,E)$, a partition $S ...
0
votes
0answers
41 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
0
votes
0answers
30 views

Is there a special name for a k-connected component that is not k+1 connected?

When removing all bi-connected components from a graph I'm left with a number of connected components, but they are also not bi-connected. Is there a special name for those components?
0
votes
0answers
37 views

Illustrate this proof about transversals with an example. Is there a typo?

Let $F = \{S_1,\dots,S_m\}$ and $G = \{T_1,\dots,T_m\}$ be two collections of subsets of a finite set $E$. A transversal for $F$ is a list of elements $s_1,\dots,s_m$, one coming from each set in ...
0
votes
0answers
19 views

Tradeoff between graph diameter and graph connectivity

Let $G$ be a graph with the property that, for every node, no more than $n^b$ nodes lie within distance $n^d$ of that node. Can we use this information to infer that the graph diameter (max distance ...
0
votes
0answers
49 views

how to calculate the minimum edge cut set number of a graph

Given a graph, there are several kinds of minimum edge cuts. How to calculate how many cuts in the minimum edge cut set? Is there any algorithm solving this problem? Thank you!
0
votes
0answers
22 views

Multiple Attachment to the Same Node in Barabasi-Albert Model

In the Barabasi-Albert Model, is a newly introduced node allowed to attach more than once to the same node? The master equation does not seem to include terms describing nodes gaining more than one ...
0
votes
0answers
17 views

How to estimate the edge count of a social graph?

How do I get a rough count of the number of edges in a social network graph / scale-free network, depending on its typical parameters like user count (vertices), number of contacts or maybe clustering ...
0
votes
0answers
30 views

Depth in acyclic graphs

I am struggling to understand a definition in a paper: Given a acyclic (directed!) graph $D=(V,E)$ we define a sequence $Q_i \subset V(D)$ of sets: $$Q_0 = \emptyset,$$ $$ Q_i \textrm{ is ...
0
votes
0answers
65 views

How I can prove euler characteristic of this complex is zero

$P$ is the poset of all nonempty subsets of $\{ 1, 2, 3, ....,n\}$ under set inclusion. Show that reduced euler characteristic of $\Delta P$ = $ 0$ I tried induction... but failed.
0
votes
0answers
30 views

Computing an element of Moore-Penrose pseudoinverse of a large sparse matrix

I am computing resistance between two points in a network. To do this I compute the Laplace matrix and then take a Moore-Penrose pseudoinverse. However, I am really only interested in the resistance ...
0
votes
0answers
16 views

Shannon capacity

Let $G$ be a graph whose Shannon Capacity is $\Theta(G)$. Is there any graph product for which the Shannon Capacity is $\Theta(G)^k$ where $k$ is the number of times the product is taken?
0
votes
0answers
36 views

How to show that a certain graph always admits three different Hamilton paths?

Let $G=(V,A)$ be a graph in which every pair of vertices $k_i , k_j \in V (i \neq j)$ is connected by some arrow $(i,j) \in A$. Let's call this graph a tournament. Furthermore, let this tournament be ...
0
votes
0answers
18 views

When is the edge-covering number equals the edge-independent number?

Is there a necessary and sufficient condition that the edge-covering number of a graph $G$ is equal to the edge-independence number? A sufficiency of this is when $G$ is bipartite, but is the equality ...
0
votes
0answers
31 views

Graph theory Centrality

I am trying to work out centrality in a network using Freeman's network centrality. I have an in degree of 83 and an out degree of 110. I want to work out the network centrality using my out degree ...
0
votes
0answers
34 views

An independent set of vertices $\times$ the chromatic number $\ge$ the number of vertices

$A$ is a graph. By definition an independent set $S$ is a group of vertices (could be 0 vertices, or could be all vertices) of $A$ where there are no two vertices from $S$ that are adjacent in graph ...
0
votes
0answers
28 views

An interleaved path of arrows in a category/digraph

In what I am doing now, a slightly strange concept emerged; My objects are sequences of arrows $\{f_i\}_{i=1}^{n}$ in a small category such that for every $1\leq i\leq n-1$, there is an arrow from the ...
0
votes
0answers
35 views

Dimension of cycle space of $G$ less than or equal to that of a subgraph $H$?

So let $G$ be a graph with subgraph $H$. I need to prove the dimension of the cycle space of $G$ is equal to or less than the dimension of the cycle space of $H$, which I understand to be the nullity ...
0
votes
0answers
34 views

Determine line crossing corner of cuboid and POV of a camera faced towards it, based on the angles in the photo

Say you were to take a picture to a corner of a room with 90 degree angled walls and ceiling. In that picture you'd see three radial lines (the edges of the walls) starting in the same point (the ...
0
votes
0answers
35 views

Algorithmically constructing graphs with specified degrees

In graph theory books there are lots of problems similar to these: Construct a graph of 7 vertices with exactly 5, 2, 1, 1, 1, 1, 1 degrees Prove or disprove that there is graph of 4 vertices with ...
0
votes
0answers
35 views

Reversing a random walk on a hypergraph

I'm looking for resources (books, papers, etc) that will suggest how to reverse random walks on an invariant directed hypergraph. If you're curious, more details are below. In my problem, I allow a ...
0
votes
0answers
37 views

A problem in graph transformations.

I was going through a paper on graph transformations: see here. I can't understand a concept introduced there. I am giving an extract from that paper below ($VG_1$ denotes the set of vertices of a ...
0
votes
0answers
37 views

Map Subgraph Ismorphism Problem to SAT Problem

The Subgraph Isomorphism (SI) problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. I want to ...
0
votes
0answers
15 views

examples of Voronoi diagram for which each region of the diagram has at least 3 vertices, on average.

Let us assume P is a set of n points and V is the set of vertices in the Voronoi diagram, E the set of edges. Assume n>=3, not all points collinear. Show that there are examples of P for which the ...
0
votes
0answers
37 views

Maximum independent set problem

I need to study about the maximum independent set problem in graph theory. I need to study the $P_t$ free graphs and many other such variants and look up their maximum independent set characteristics. ...
0
votes
0answers
33 views

Threshold function for non-balanced graphs counter example

Let $G(n,p)$ be a random graph and let $H$ be a balanced graph with $e$ edges and $v$ vertices.. We know that $p^{*}(n)=n^{-v/e}$ is the threshold function for containing a copy of $H$. That is, if ...
0
votes
0answers
29 views

number of k-plex in a random graph

I saw Moon & Moser (1965) result on the bound on number of maximal cliques in a graph that any n-vertex graph has at most $n^{n/3}$ maximal cliques. Is there any similar results regarding the ...
0
votes
0answers
38 views

Standardizing the terminology of graph theory

I took a course in graph theory many years ago and remember being frustrated that the terminology was not at all standardized (or didn't seem to be). Various sources used vastly different words or ...
0
votes
0answers
21 views

Finding the number of nodes with known number of hops to a particular node

Assuming all links have a weight equal to 1 in a sample graph. Is there any algorithm that counts the number of nodes with specific shortest path (i.e. hops, in this case) to a destination node ? For ...
0
votes
0answers
18 views

Cardinality of maximum matching for $G=<V,E,w>$

I have to find the cardinality of the maximum matching for graph $G=<V,E,w>$ with weights on the vertices, whose edges fullfill the following formula: $$\forall x,y\space (x,y) \in E(G) ...
0
votes
0answers
13 views

What's the name for the union of a set of any graph and the set of its related hypergraphs?

So any graph can, if you arbitrarily partition the vertices into two groups represent, in that bipartite form, the incidence graph of a corresponding hypergraph. Is there anything special or known ...
0
votes
0answers
43 views

Proof for ACYCLIC PARTITION being an NP-complete problem

I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers. I'm interested in reading any proof of ACYCLIC PARTITION (Garey and ...
0
votes
0answers
32 views

Partition complete graphs

If I have $K_n$, and I want to partition edges of $K_n$ into edges sets of complete graphs $G_1,...G_k$, then I need to show $n \le k$. My approach was thinking of $K_5$ which is a partition of $5$ ...
0
votes
0answers
33 views

Adjacency matrix of strongly connected digraph

If I have $A$ the adjacency of a strongly connected digraph, I want to show: For $\lambda$ satisfying $Ae= \lambda e$ for nonegative $e$, I want to show for any eigenvector (could be negative), the ...
0
votes
0answers
29 views

Can an arbitrary network of nodes be effectively visualized as a circular “treemap”?

We all know that a treemap is effective for visualizing hierarchical tree data (i.e. where there are only 1 to many relationships like in a computer file system): But how difficult algorithmically ...
0
votes
0answers
17 views

Generalization of size reduction of Linear Assignment Problems

It is well known, that the LAP has super linear complexity. Hence, problem-size reduction is a viable optimization strategy. For instance, if one task is incident to exactly two workers, one can ...
0
votes
0answers
40 views

Edge Connected Proof

Prove that if $G$ is a $k$-edge-connected graph and $e$ is an edge of $G$, then $G-e$ is $(k-1)$-edge-connected. Assume that $G-e$ is not $(k-1)$-edge-connected. Then there exists a set $X$ ...
0
votes
0answers
32 views

Who proved Dirac's thoerem?

I was browsing wikipedia page on Paul Dirac and I found under things he is known for Dirac's theorem about Hamiltonian graphs. But while browsing this other article on Gabriel Andrew Dirac I found the ...