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

4
votes
1answer
78 views

Free product as automorphism group of graph

Let $A$ and $B$ be two groups. We define following graph $X$. The set of vertices is the left cosets $gA$ and $gB$ where $g\in A*B$ (By $A*B$, I mean the free product of $A$ and $B$). The edges of the ...
0
votes
0answers
10 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
18 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 ...
1
vote
1answer
130 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
0
votes
0answers
17 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 ...
3
votes
1answer
49 views

Programmatically recognizing symmetries of a polyhedron

I'm programming something, but I'm stuck at something which more math-oriented people probably can help me with. I am giving a polyhedron in the following form: for each vertex I get the cyclic order ...
0
votes
0answers
11 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
62 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 ...
1
vote
3answers
67 views

May directed graph be embedded into manifold?

May directed graph be embedded into manifold?How ?and what is the condition?
0
votes
1answer
47 views

Assigning $\pm 1$ values to the edges of a complete graph

I read this sentence in one combinatorics book. In graph $K_{100}$, there is a possible way to assigns number (value) from $\{+1,-1\}$ to each edge, so that the sum of all edge values connected to ...
1
vote
0answers
34 views

Prove that a graph $G$ that is isomorphic to its dual is not bipartite

Where $G$ is a simple connected graph and has $\ge 2$ vertices. I'm trying to understand the answer from Proving a graph is not bipartite but I don't understand this is true. ...
3
votes
1answer
176 views

Mathematician who talked about the probability of a “good” graph?

In my undergraduate years, one of my professors always talked about this one mathematician who was talking about "good" graphs and wondered about the existence of such a graph. Apparently this ...
1
vote
0answers
19 views

minimum number of unit distances required for a unit equilateral triangle

Problem. Suppose we have $n$ points on the plane. Among $\binom{n}{2}$ pairwise distances, there are $e$ number of unit distances. Find minimum $e$ ($e$ as a function of $n$) so that there is a ...
4
votes
0answers
46 views

Is a connected graph uniquely determined by its weighted 2-step graph? [migrated]

This is an extension of a previous question: Is a graph uniquely determined by its weighted 2-step graph?. In that question I asked about arbitrary graphs; in this question I restrict to connected ...
0
votes
1answer
14 views

Simple question about indexing edges of an undirected graph.

As far as I understand, for an undirected graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$, the set of edges is defined as unordered 2-element subsets of $\mathcal{N}$. So, for example, $\mathcal{E} = ...
1
vote
0answers
31 views

Probability that a subset of a degree-regular graph shares at least a certain number of mutual connections

Consider a set of $n$ vertices of common degree $p$. What is the probability that some subset of $x$ vertices from $n$ share $q$ mutual connections within that group of size $x$? i.e. If we have ...
6
votes
0answers
121 views

Parity of sum of Kronecker deltas in a graph

For some fixed $n\in\mathbb N$ let $G$ be a graph on the vertex set $\{1,\dots,n\}$ with a total number of $k$ edges $e_1,\dots, e_k$. For any vertex colouring $c(i)$ of the graph, $\delta_e$ is ...
0
votes
1answer
31 views

Graph isomorphism problem for labeled graphs

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
0
votes
2answers
41 views

Prove that if G is a tree in which all vertices have odd degree then G has odd size.

Prove that if G is a tree in which all vertices have odd degree then G has odd size. Good night, do not know how to approach this "prove". Can you give me tips to solve it?. Please.
4
votes
0answers
22 views

Largest Matching whose removal does not leave Eulerian components

Task: Given an undirected graph $G = (V, E)$, find a largest matching $M \subseteq E$ such that $G-M$ has no Eulerian components (i.e. all connected components of $G-M$ must have odd-degree ...
1
vote
0answers
33 views

directed simple graph, all paths from node $ v_0 $ to an other node $ v $, MATLAB

consider a directed simple graph $ G=(V,E) $ with $ V=\lbrace v_0,v_1,\ldots,v_k \rbrace $ and adjacency matrix $ A=(a_{ij}) $, where $ a_{ij}=1 $ means, that there is an arc from node $ v_i $ to node ...
0
votes
1answer
18 views

What is the difference between `Cross edge` and `Forward edge` in a DFS tree?

In the most general way, Let $G(V, E)$ be a graph, and $T(V', E')$ be the DFS tree of $G$. If an edge $(u, v) \in E'$ is neither a tree edge nor a back edge, How can we determine whether it's a ...
2
votes
1answer
43 views

Is a graph uniquely determined by its weighted 2-step graph?

Let $G$ be an undirected graph. Define the 2-step graph $G^{(2)}$ of $G$ to be the weighted graph whose vertices are the same as those of $G$ but whose edges correspond to 2-step paths in $G$. Thus ...
9
votes
1answer
142 views

Graph partition that span a third of edges

Given a graph G is easy to see that we have a partition $V=V_1 \cup V_2$ so that $$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that ...
0
votes
2answers
27 views

How to find a pointset with unique distances

Is there a way to arrange N number of 2D points within a box so that the distances between the points are unique? I have an application where I can measure the distances between points with some ...
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
1answer
39 views

Crossing edges at space

Let's say I have Graph $G(v, e)$ I want to draw the graph without crossing edges on space. By giving $(x, y, z)$ for any Vertex. How can I check if one edge crosses another?
0
votes
2answers
29 views

Proof d-regular graph has an equal number of vertices in its bipartition

Let $G$ be a $d$-regular graph. Suppose that $G$ is bipartite with bipartition $(A,B)$. Prove that if $d>0$ then $|A| = |B|$. Also why is this statement false when $d=0.$ I'm not sure how to show ...
2
votes
2answers
50 views

Graph containing every trees of size $n$ as subgraphs

What is the minimum number of edges of graph $G$, so that every tree of size $n$ is a subgraph of $G$? I personally managed to find a lower bound of $c n \log n $ and an upper bound of $C n \log ...
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
1answer
32 views

Find a kernel in a directed graph.

It's a question from a sample exam I'm trying to solve but with no success yet. Let $G(V, E)$ be a directed graph. set $A \subseteq V$ is a kernel if: i. $\forall u,v\in A \implies (u, v), ...
0
votes
1answer
27 views

Finding all mapping between two isomorphic graphs

Is there any formula for counting all the mappings between two isomorphic graphs? I have the following two graphs. and I am trying to find the mappings in the following way. For each edge in ...
1
vote
1answer
17 views

Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
0
votes
1answer
34 views

Removing cycle from the complete graph.

How can I remove $6-length$ cycle from the $K_6$ complete graph so that it'll result a $K_{3,3}$ bipartite graph? I've tried a couple of ways, but I can't get needed result. Maybe this decomposition ...
-1
votes
0answers
44 views

Count suggestions to be send

A site currently has N registered users. As in any social network two users can be friends. We wants the world to be as connected as possible, so we want to suggest friendship to some pairs of users. ...
-1
votes
1answer
47 views

Friends meeting at point

N friends live in different houses spread across the city.There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same ...
23
votes
4answers
577 views

Is this graph connected

Define the following graph on the vertex set ${\mathbb N}_{\geq1}\>$: Two numbers $a$, $b\in {\mathbb N}_{\geq1}$ are connected by an edge (written $a \ \mathcal{R} \ b)$ if and only if $a+b \ | ...
1
vote
3answers
72 views

Proof of an $\iff$ statement on binary trees

Let $x$ and $y$ be two nodes of a binary tree $B$. Prove that $x$ is an ancestor of $y$ $\iff$ $x$ stands before $y$ in the pre-order traversal of $B$ and $x$ stands after $y$ in the ...
0
votes
2answers
101 views

Planar graphs where every face boundary is a cycle of even length are bipartite

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. If every face boundary is a cycle of even length, ...
0
votes
1answer
88 views

3-regular connected planar graph

Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one face of degree 4. Determine the number of ...
1
vote
3answers
30 views

Find an odd-length cycle in an undirected graph.

I have an exam next week and I found a question that I have difficults to solve: Given the following: Input: Simple undirected graph $G(V, E)$. Output: Find an odd-length cycle in $G$ or ...
0
votes
1answer
22 views

Let $H$ be a simple graph on $n$ vertices that has $m$ edges. Prove that $H$ contains at least $m-n+1$ cycles.

Can someone please verify the proof I just wrote, or offer suggestions for improvement? Also, how do I prove the base case? Let $H$ be a simple graph on $n$ vertices that has $m$ edges. Prove that ...
0
votes
1answer
21 views

If $G$ is connected then $\lambda_2 < \lambda_1$.

Let $G=(V,E)$ be an $n$-vertex , undirected graph with maximum degree $d$, then how to prove the following result. If $G$ is connected then $\lambda_2 < \lambda_1$. where $\lambda_1 \geq \lambda_2 ...
0
votes
0answers
42 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 ...
2
votes
0answers
31 views

Counting symmetric binary matrices with constant line-sum

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a ...
1
vote
3answers
34 views

Graph Realization Problem

Given degrees of nodes, is it possible to construct a graph with those degrees, and if yes devise the algorithm? I know of Handshaking Lemma that describes my problem, and another algorithm for it as ...
2
votes
2answers
46 views

Tutorial on Complex Networks

Can anyone advise mea nice and short tutorial about Complex Networks? I'm reading "Networks: An Introduction" from Mark Newman, and is a bit tedious... Thanks PS: There isn't a tag "complex networks" ...
2
votes
1answer
44 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
0
votes
1answer
59 views

What is a `red vertex` and what is a `blue vertex`?

I showed the following question on an exam: let $G(V, E)$ connected indirected graph with positive weights. any vertex is colored with either blue or red. Claim: if edge $(u, v)$ is the ...
2
votes
1answer
53 views

A basic question on random graph

Consider undirected graphs with $n$ vertices. now consider the set of all possible edges (excluding self-loops). now, select edges from the set with probability $p$ independent of the other edges. so, ...