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

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

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 ...
-3
votes
0answers
33 views

Bipartite Graph Maximum Edge [on hold]

As i post it yesterday, i post it again with my thought. we know that, A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. That is, every vertex of the graph ...
-4
votes
0answers
26 views

Graph Edge Number Calculation [on hold]

I read this sentence in one answer sheet of exam. anyone could describe it for me, and say sth about proof of this sentence. Maximum number of edges in bipartite graph which has no Matching with 10 ...
0
votes
1answer
9 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
20 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 ...
1
vote
0answers
27 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 ...
-3
votes
0answers
47 views

Maximum Number of Edge Problem [on hold]

I read this sentence in one answer sheet of exam. anyone could describe it for me, and say sth about proof ot this sentence. Maximum number of edge in bipartite graph with has no Matching ...
0
votes
1answer
27 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
34 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
21 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
20 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
16 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
21 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 ...
1
vote
0answers
22 views

Find all simple graphs with exactly one pair of vertices of the same degree. [on hold]

A simple graph is a graph with no loops or double edges. Find all simple graphs with exactly one pair of vertices of the same degree.
7
votes
1answer
90 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
25 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
33 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
37 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
22 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
47 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
20 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
29 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
26 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
14 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
32 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
1answer
45 views

Is the following graph chordal? [on hold]

A very simple question: Is the following graph a chordal graph?
-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
45 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 ...
19
votes
3answers
421 views
+100

Is this graph connected

Define the following equivalence relation $\sim$: We have $a \ \mathcal{R} \ b$ if and only if $a+b \ | \ ab-1$. $a \sim b$ if and only if there exist a sequence of integers $a_1, \ldots, a_n$ such ...
1
vote
3answers
70 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
94 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
85 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
25 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 ...
-3
votes
0answers
44 views

Party-dance-boys-girls [closed]

At a party,there are $n$ boys and $n$ girls.Each boy danced with exactly $k$ girls and each two boys danced with exactly $d<k$ common girls.Show that each girl danced with exactly $k$ boys and each ...
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
23 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
1answer
36 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
42 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
57 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
49 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, ...
2
votes
2answers
37 views

Calculating the central point with minimal average distance to other points

I work at an office with colleagues coming from all over the country. Our office is quite centrally located, but some colleagues have to travel quite a lot further than others. I often wondered how I ...
5
votes
0answers
30 views

Name for Number of Ancestors/Descendants of Vertex in Directed Acyclic Graph

Let $G = (V, E)$ be a directed acyclic graph. For each vertex $v \in V$, define the ancestors of $v$ to be the set of vertices $u \in V$ such that there exists a directed path from $u$ to $v$. ...
2
votes
0answers
104 views

a closed formula to enumerate the self avoiding walks of a graph

Let $G$ be a directed graph with $N$ nodes and weighted adjacency matrix $W $ defined by $$ W_{ij} = \left\{ \begin{array}{cl} w_{ij} & \text{ if } \ i \ \text{ is connected to } j \\ 0 & ...
7
votes
1answer
80 views

The rows continue to be different to each other

In each position of an $n \times n$ matrix there is a number. We know that all the rows of the matrix are different from each other. Show that we can delete a column so that the rows of the matrix ...
0
votes
0answers
20 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
1answer
21 views

The “sides” of a k-regular bipartite graph are equal?

I was reviewing some lectures notes and noticed that in a proof of a theorem our lecturer stated that the "sides" of a k-regular bipartite graph are equal and that it is trivial to prove it. Anyway ...
3
votes
0answers
37 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...