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
0answers
15 views

Graphs and Trees: discrete math [on hold]

Construct a graph based on the adjacency matrix that appears below. Label all nodes with indices consistent with the placement of numbers within the matrix. \begin{pmatrix} 0 & 6 & 0 & 5 ...
0
votes
1answer
12 views

How many graphs can have the same line graph?

Suppose we have a finite simple graph $G$. Call $\mathcal O$ the set of graphs without isolated vertices up to isomorphism whose line graph is isomorphic to $G$. Can $\mathcal O$ contain more than one ...
1
vote
0answers
34 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
0
votes
1answer
24 views

How would you incorporate probability into this graph theory problem?

A non-closed path is chosen at random on the complete graph K9. All paths are equally likely. What is the probability that the path contains the edges {23} and {34} given that it is length 6? Given ...
0
votes
1answer
17 views

Hamiltonian cycle adjacency sum Proof

Let $C$ be a Hamiltonian cycle on a graph with vertices labeled {$1,...,9$}. Prove that there are $3$ vertices adjacent in $C$ whose labels sum to at least $12$. I understand why this fact is true by ...
0
votes
1answer
22 views

Calculating the number of isomorphic classes of complete bipartite graph

How many isomorphism classes of complete bipartite graphs have exactly 10 vertices? I don't understand what the question is asking or how to go about solving it.
-1
votes
0answers
31 views

Construction of a Huffman tree

My task is the following: Provide an example for the following: A complete Huffmann tree with $n=5, q=2$, lengths $l_1,......,l_5$ and $l_1>l_2>l_3>l_4$. (Draw the tree and give weights ...
1
vote
3answers
61 views

Recurrence solution of simple recurrence

Please help me to find the solution of the recurrence in terms of n(implies $(f(n))$ and also the summation of the recurrence up to infinity ($sum = \sum_{n=0}^\infty f(n)$) . ...
1
vote
1answer
25 views

Clustering analysis of a weighted graph

My data consists of a large weighted undirected graph of $n$ nodes. I need to group the nodes into $m$ clusters ($m < n$), such that nodes in a cluster are connected with heavy weights. What ...
1
vote
0answers
23 views

Maximal flow in flow-networks

I want to do the task (b),(c) and (d)in the picture above. I have done (b) correctly. For (c) I only found one (s-t) augmenting path, namely (s,1),(1,3),(3,2),(2,4),(4,t) and I only can push one ...
0
votes
1answer
13 views

Can the number of cycles in non-planar undirected graphs be computed in reasonable time?

Background: I'm experimenting with programs that create non-planar undirected graphs from three-dimensional meshes. A graph created by program A is not necessarily isomorphic to one created by program ...
0
votes
0answers
27 views

Miscellaneous questions about trees

I want to know which of the following claims are true: 1) Let T be a minimal spanning tree in G for a weight function w. Then T is also a minimal spanning tree for the weight function obtained from w ...
0
votes
1answer
18 views

Proof about spanning tress in graphs

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$. Let $f_1 \in F_1$. Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.
0
votes
2answers
22 views

Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.

In a complete graph with $n$ vertices there are $\frac{n−1}{2}$ edge-disjoint Hamiltonian cycles if $n$ is an odd number and $n\ge 3$. What if $n$ is an even number?
4
votes
1answer
58 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
9 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
17 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 ...
0
votes
0answers
32 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
12 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
30 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
10 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
55 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
59 views

May directed graph be embedded into manifold?

May directed graph be embedded into manifold?How ?and what is the condition?
0
votes
1answer
46 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
33 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
170 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
16 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
43 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 ...
0
votes
1answer
12 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
29 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 ...
5
votes
0answers
75 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 ...
0
votes
1answer
29 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
36 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
25 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
38 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. [closed]

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
113 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 ...
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
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
38 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
24 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
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 ...
0
votes
0answers
21 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
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
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?