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

1
vote
0answers
71 views

3-connectedness Expansion Lemma

The question is as follows: Prove that applying the expansion operation* to a 3-connected graph yields a 3-connected graph. *The expansion operation is as follows: you take two edges of a graph ...
1
vote
0answers
42 views

Help understanding KL-Divergence

I will be doing a course in Information Theory soon and to get some early learning in I have been attempting a question with a joint probability mass function represented by the following table: In ...
1
vote
0answers
21 views

Graph having the same genus

Let $G$ be a finite simple undirected graph of genus $g$. We construct a new graph $H$ from $G$ as follows. $V(H)=V(G)\cup K$ and $E(H)=E(G)\cup L$, where $K:=\{v_{ab} \mid a,b \in V(G)$, $a$ and $b$ ...
1
vote
0answers
48 views

Which in graph theory book do you recommend for a Biologist?

I need a book in Graph Theory for my Thesis project in Biology (6 months from now). I have reasonable mathematical knowledge. The book must be strict but not as complicated as an advanced book. The ...
1
vote
0answers
134 views

“Dual cardinality” in the graphs $(V_\alpha,\in_\alpha)$

04-25-2014 Enriched with more details Let define the graphs $(V_\alpha,\in_\alpha)$ in $ZFC$ $V_\alpha$ can be finite too $\in_\alpha \subseteq V_\alpha \times V_\alpha$ and ...
1
vote
0answers
100 views

Size of $V$ to guarantee $k$-paradoxical tournament.

It was proven by Erdos that for any $k$ there exists a $k$-paradoxical tournament, as described here: http://en.wikipedia.org/wiki/Tournament_(graph_theory)#Paradoxical_tournaments. I am able to show ...
1
vote
0answers
43 views

Determining the matching number of a graph given maximal matchings.

Let $G$ be a graph with maximal matchings $M_1$ and $M_2$, with $3$ and $6$ edges, respectively. Determine the matching number of $G$. The only progress I've been able to make is that $M_1$ and ...
1
vote
0answers
34 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...
1
vote
0answers
105 views

Does any vertex transitive graph have a bounded eigenvector?

Following up on the negative answer to this question, I would be interested in knowing the answer to the following question, which I cannot seem to find an obvious contradiction to when testing for ...
1
vote
0answers
76 views

How to answer the following question related to counting the number of trees of a graph?

I am asked to prove the equality $$ 2(n-1)n^{n-2} = \sum_{k=1}^{n-1} \binom{n}{k} k(n-k)T(k)T(n-k) , $$ where $T(k)$ is the number of different trees with $k$ numbered vertices. I think the ...
1
vote
0answers
29 views

Decentralized Algorithm for a one dimensional ring

I'm working on a homework in which a graph of n nodes is arranged as a one-dimensional ring and every node has 3 out-going edges. I need some help in proving that any decentralized algorithm would ...
1
vote
0answers
88 views

Number of Nodes within a Given Distance from a Node

Suppose we are given a $d$-regular graph $G=(V,E)$ of order $n$. Let $\lambda_2$ be the second-largest eigenvalue of $G$'s adjacency matrix. Does this information help obtaining a lowerbound or ...
1
vote
0answers
39 views

Finding coordinates of nodes in a graph

I have a complete graph in which the edges represent the euclidean distance between the nodes which is known. Assuming a node to be (0,0), I want to find (approximately) the coordinates of other ...
1
vote
0answers
58 views

k-sum in weighted DAG

Is there a known algorithm that solves the following problem: Given a directed acyclic graph $G$ with weights on the edges, all nodes have a blue color. We seek to color with red every path $P$ with ...
1
vote
0answers
72 views

Distance matrix of connected graph always invertible?

I know there's a question elsewhere about distance matrix for points on Euclidean plane, but I'm not sure if that one was relevant. Anyway, given a connected (simple) graph G with $n$ vertices ...
1
vote
0answers
48 views

Random walk on a graph

For a random walk say from point $x$ to $y$ on a graph, How is the probability of a Random walker reaching point $y$ before returning to $x$ related to the expected of the number of visits to point ...
1
vote
0answers
60 views

automorphisms of the infinite trivalent tree

Let $T$ be the infinite trivalent tree. I want to show that if $\alpha,\beta,\alpha',\beta'$ are vertices of the tree such that the distances $d(\alpha,\beta)$ and $d(\alpha',\beta')$ are equal, then ...
1
vote
0answers
52 views

Upper bound for constant weight code L(n,d,w), with n=128, d=4

I would like to find an upper bound: L(n,d,w) <= f(n,d,w) for a constant weight code L(n,d,w), where w is the maximum weight, d is the Hamming distance between codes, and n is the code length. I ...
1
vote
0answers
64 views

2 simple doubts about graph theory problems

The first one: In this exercise I am asked to compute the number of 4-regular graphs of order 7. I had an idea but I don't really know if it is the correct way of proceeding: In a graph of order 7, ...
1
vote
0answers
202 views

Every Edge of a graph is either Contractible or Deletable

I need to Show that Every edge of a 2- Connected graph is either contractible or Deletable. Contractible Edge:- To contract an Edge, remove it and its end points(vertices) should be merged along with ...
1
vote
0answers
61 views

Under what conditions is there a common transversal?

Let $S = \{S_1,\dots,S_n\}$ and $T = \{T_1,\dots,T_n\}$ be two collections of finite subsets of $\{1,2,\dots\}$. A transversal for $S$ is a list of elements $s_1,\dots,s_n$, one coming from each ...
1
vote
0answers
582 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
1
vote
0answers
46 views

showing that all convex polehedron graphs are 3-connected

I'm trying to figure out how to show that two nonadjacent vertices in the graph of a convex polyhedron can be disconnected from one another by the removal of at least three vertices. I know what a ...
1
vote
0answers
38 views

Conditional covariance in gaussian graphical models

I have a hypothesis, but I'm not sure if its true. The Wikipedia page states that if the covariance matrix is given by $$\Sigma=\left[\begin{matrix} A & B \\ B^T & C \end{matrix}\right]$$ ...
1
vote
0answers
49 views

Number of nodes with degree d in a graph

Why the number of nodes with degree $d$ in a graph $G$ is equal to the number of copies of $d$-stars in $G$ that are not part of any $(d + 1)$ star in $G$ ? Isn't it possible to have nodes with ...
1
vote
0answers
71 views

Prove that the minimum of row sums of a nonnegative symmetric matrix is preserved

Let $A$ be an $n\times n$ adjacency (nonnegative, irreducible and symmetric) matrix with zeros on the diagonal. Denote $i$-th row sum of $A^k$ as $r^{(k)}_i$, where $k\geq1$. I want to prove that if ...
1
vote
0answers
57 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 ...
1
vote
0answers
71 views

A question regarding a prefix code

Let $C=\{ c_1, c_2, \dots, c_m \}$ be a set of sequences over an alphabet $\Sigma$ and $|\Sigma|=\sigma$. Assume that $C$ is a prefix-free code, in the sense that no codeword in $C$ is a prefix of ...
1
vote
0answers
26 views

Genus of a simple graph $G$.

Let $G$ be a simple graph with set of vertices $V(G)=\{a_i,v_j \mid 1\leq i \leq 5, 1\leq j \leq 4\}$ and the set of edges is ...
1
vote
0answers
102 views

Proof of Gallai's Theorem for Critical Graphs

A fundamental theorem in Graph theory is the following: Let $G$ be a $k$-critical graph with $k\geq 4$ and $G\neq K_k$. Then every block in the subgraph of $G$ induced by the vertices of degree $k-1$ ...
1
vote
0answers
225 views

Detect an odd-length cycle from a directed graph

so my goal is to detect an odd-cycle in a directed graph. I know for the undirected graph, the graph contains the odd-cycle iff it's non-bipartile. So I can check whether or not the graph is ...
1
vote
0answers
43 views

Graph diameter of a single vertex?

Convention-wise, given the simple graph with a single vertex, what is the graph diameter? I can see three options, zero, since there is a trivial path from the vertex to itself. infinity, since ...
1
vote
0answers
75 views

Probability that the network is connected in an unstructured p2p network

Suppose that three nodes form an unstructured p2p network (a network where each node has a list of neighbors node, in which there are addresses of c live neighbors) and each selects to cache the IP ...
1
vote
0answers
117 views

Is the singleton graph 2-connected?

Whether the singleton graph is connected, depends on the definition: (1) A graph is said to be connected if every pair of vertices in the graph is connected. (Wikipedia, Connected graph) ...
1
vote
0answers
20 views

On Special Deviations of a Score Sequence

Can anyone help me to my problem? First of all, I will introduce the definition of deviation sequence, and special deviations. Let $<S_1,...,S_n>$ be any sequence of integers. The ...
1
vote
0answers
160 views

Adjacency matrix of directed graph

I am given adjacency matrix $A$ of directed graph. $A(x,y)$ counts the number of edges from $x$ to $y$. I want to show that if $A$ has constant outdegree $d$: (i) For any eigenvalue $\lambda$, we ...
1
vote
0answers
54 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seem to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...
1
vote
0answers
36 views

Number of Isolated Edges in G(n,p)

I am attempting to find the number of isolated edges in the Erdos - Renyi graph G(n,p). I need to find the formula for the expected number of isolated edges. I've broken the equation down into ...
1
vote
0answers
37 views

Determine the condition on $n$ for $W_n$ to be critical graph.

The way my professor defines $W_n$ is the wheel graph of $n + 1$ vertices. That is, the graph with $n$ vertices, each adjacent to the vertex of degree $n$, in the cycle. We assume $W_n$ is a simple ...
1
vote
0answers
174 views

Set Theory , Konig's Lemma and Infinite Graph Theory

I am trying to understand the basics of Infinite Graph theory and various preconditions in Konig's Lemma. The texts I have studied tend to use the Axiom of Choice (usually Zorn's Lemma) as a tool of ...
1
vote
0answers
53 views

How do I apply vertex or edge coloring to my DAG problem?

I am working on solving a DAG (Directed Acyclic Graph) problem and the part I care about is edge direction and how many ways I can assign directions (while staying acyclic) without making a ...
1
vote
0answers
68 views

Proof of existing path on Depth-First-Search spanning tree

Let $G$ be an undirected connected graph, and $T$ the directed spanning tree of $G$, which I got by performing a DFS on $G$. If $H$ is a complete subgraph of $G$, how can I proof that there a path in ...
1
vote
0answers
50 views

How we show primitive action shows alternating group

I have a graph (as shown in figure), which represents a quotient of the group $$G=\langle A,B,C,D; A^3=B^2=C^3=D^2=(AC)^2=(AD)^2=(BC)^2=(BD)^2=1 \rangle.$$ I proved that $G$ acts 2-transitively and so ...
1
vote
0answers
33 views

Probability of inter-group links in a network with maximum degree 1

In an undirected network, there are two groups of nodes. Group 1 has N1 nodes, and group 2 has N2 nodes. The links in the network are generated following such rules: (1) The maximum degree is 1, ...
1
vote
0answers
427 views

Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time.

So we have a graph $G$ with its edges colored by red and blue. we are asked to find a deterministic linear time algorithm that given a parameter $K$ finds a spanning tree of G using exactly $K$ red ...
1
vote
0answers
84 views

References for Hyperbolic Graph Theory

I'm sorry to disturb you but I really got stuck! I can't find any clear and, somewhat, complete reference for this topic. I'm looking for a book, or review, or survey or course notes regarding ...
1
vote
0answers
68 views

Matchings in $G=(V,E)$ be an undirected graph, and let $S,T\subseteq V$ be two sets of vertices with no common neighbors

Let $G=(V,E)$ be an undirected graph, and let $S,T\subseteq V$ be two sets of vertices with no common neighbors (there can be edges between $S$ and $T$). We need to show that if there exists a ...
1
vote
0answers
49 views

pierre simon laplace and his knowledge of the (Laplacian) matrices

so as we all know, there is a graph matrix called the Laplacian that is used in some eigenvalue/eigenvector/graph theory/spectral theory problems. i'm wondering if the name of this matrix is ...
1
vote
0answers
39 views

How to show that the spectral radius of a binary tree approaches exp(1) as the N tends to infinity?

How can I prove mathematically that the spectral radius of a binary tree approaches e as the number of nodes tends to infinity? I mean it is true that the increase in nodes number is exponential but ...
1
vote
0answers
42 views

Determine the number of simple 7-vertex, 4-regular graph that are pairwise non isomorphic.

I'm taking an introductory graph theory course and I am having trouble going about answering this question. I've been told to look at the graph compliment but I don't quite understand how that ties ...