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

2
votes
1answer
29 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
3answers
54 views

May directed graph be embedded into manifold?

May directed graph be embedded into manifold?How ?and what is the condition?
7
votes
1answer
99 views
+50

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 ...
-1
votes
0answers
74 views

Bipartite Graph with Maximum Edges

I am trying to solve a problem in extremal graph theory: Find the maximum number of edges possible in a bipartite graph that (a) has no matching with ten edges, and (b) contains no star of 8 ...
20
votes
3answers
487 views
+100

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 \ | ...
0
votes
0answers
7 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
41 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 ...
3
votes
0answers
53 views
+100

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 ...
4
votes
2answers
360 views

Proving a graph is not bipartite

Let $G$ be a simple planar graph with at least $2$ vertices, and let $G^*$ be the dual of a planar embedding of $G$. Prove that if $G$ is isomorphic to $G^*$ , then $G$ is not bipartite. I have ...
0
votes
1answer
41 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
29 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
166 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
15 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 ...
2
votes
0answers
27 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 ...
2
votes
2answers
48 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 ...
-3
votes
0answers
38 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
11 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
28 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 ...
2
votes
0answers
24 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
2answers
227 views

Graph Theory: Tree has at least 2 vertices of degree 1

Prove that every nontrivial tree has at least 2 vertices of degree 1 by showing that the origin and terminus of a longest path in a nontrivial tree both have degree 1. Ok, so this statement is pretty ...
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 ...
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 ...
-3
votes
0answers
54 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 ...
12
votes
3answers
464 views

Problem on bipartite graphs.

Let's $G$ is bipartite graph with sides $X=\{v_1,v_2,\ldots,v_n\}$ and $Y=\{u_1,u_2,\ldots,u_n\}.$ Let $|N_G(v_i)|=k$ and $|N_G(v_i)\cap N_G(v_j)|=d\lt k~,(i\ne j)$. Prove that $|N_G(u_i)|=k$ and ...
8
votes
1answer
254 views

What distinguishes topological spaces from graphs?

Topology would not "work" if one reverted the "direction" in the definition of continuous maps $f$: $$\text{open}(x) \rightarrow \text{open}(f(x))$$ It has to be $$\text{open}(f(x)) \rightarrow ...
0
votes
2answers
35 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.
2
votes
1answer
210 views

Why does my Barabasi Albert model implementation doesn't produce a scale free network

I'm trying to implement the Barabasi Albert model to generate some scale free network matching a power law distribution of degree. I'm using a value $m = 2$ for the main parameter of the algorithm, ...
1
vote
1answer
253 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
0
votes
2answers
26 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
1answer
30 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
2answers
23 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 ...
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
31 views

Why does an exponential random graph model belong to the exponential family?

The exponential random graph model is defined as, $$ P_\theta(Y=y)=\frac{\exp\{\theta^ts(y)\}}{c(\theta)}.$$ Where $y \in \mathcal{Y}$ the set of all possible networks, $\theta = ...
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 ...
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.
0
votes
2answers
269 views

what is the maximum number of non loop edges that can exist in an undirected graph

please tell me a equation to find maximum number of non loop edges that can exist in an undirected graph. for example if vertices are 10 then how many non loop edges can exist?
4
votes
1answer
255 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
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
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, ...
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 ...
-1
votes
1answer
45 views

Is the following graph chordal? [on hold]

A very simple question: Is the following graph a chordal graph?
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
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
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 ...
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 ...
3
votes
1answer
333 views

Maximum cycle in a graph with a path of length $k$

I don't understand why this stands: Let $G$ be a graph containing a cycle $C$, and assume that $G$ contains a path of length at least $k$ between two vertices of $C$. Then $G$ contains a cycle ...
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 ...
3
votes
1answer
205 views

Relation between articulation points and bridge edges

What is the relation ship between articulation points and bridges of a graph. Specifically, if there are no articulation points in a graph is it necessary that there will be no bridge edges.
7
votes
2answers
186 views

Rearrangement of dinner guests

A dinner host wants his guests to move, between main course and dessert, so that everyone gets a complete set of new neighbours. Guests are seated either side of a long table. Most guests have five ...
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 ...