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

0
votes
0answers
16 views

How many nodes in a K-ary tree with L leaf nodes

Assuming that we have a k-ary tree with L leaf nodes, can the average number of nodes in the tree be calculated if we were to know the average number of children for each node? If not, what other ...
0
votes
1answer
25 views

Dijkstra’s algorithm / path is this done correctly?

im doing this assignment and it seems as if my teacher has made a mistake. according to me in order to find the minimum spanning treee from a-z , you start from a and then go to : a,f,d,c,b,e,z,g ...
1
vote
0answers
14 views

Minimum vertex cover of vertex disjoint odd holes and antiholes

I am interested in knowing whether the minimum vertex cover of a graph that can be written as the union of vertex-disjoint odd holes and odd antiholes can be found exactly, in polynomial time. I could ...
-1
votes
2answers
22 views

Confusion with the reconstruction conjecture?

After reading about the reconstruction conjecture for graphs, I came up with what I thought was a proof by contradiction. Consider the class $T$ of (isomorphism classes of) finite graphs, and the ...
7
votes
0answers
69 views

Share the beer fairly in a finite number of pours

A classical problem within measurements is that you have a $8\,\text{dl}$ mug of delicious expensive beer and need to share it evenly with your friend. However you only have two empty glasses of ...
12
votes
5answers
847 views

How to show these two graphs are not isomorphic?

In my class they gave me some necessary conditions for two graphs to be isomorphic, these two graphs satisfy all of them but I don't think they're isomorphic: Degree sequences are equal. Same amount ...
1
vote
1answer
61 views

Can this expression: $\left \lfloor \left(\frac x 2 \right)^2\right \rfloor $ be rewritten without the floor part?

I was working on a graph theory problem that asks the maximum amount of edges on a bipartite graph of $x$ vertices, I got to the conclusion it should be: $$\left \lfloor \left(\frac x 2 ...
0
votes
1answer
27 views

Map one graph to another graph

consider we have a flow network $G = \{V_g, E_g\}$ and an undirected graph $T = \{V_t, E_t\}$. Nodes of the network G have weights $w(v): v \in V_g$ and edges G have weights $w(u,v): u,v \in E$. Nodes ...
0
votes
1answer
26 views

How do I approach on proving the following fact - 1. Every path is Bipartite?

I am new to Graph Theory. I have sufficient background in Linear Algebra. I found the question in the first exercise of 'Graph Theory' by Bondy and Murty.
0
votes
0answers
39 views

Relationship between the girth of a graph and the number of edges

I'm wondering if there is a relationship between the girth of a simple undirected graph and its number of edges. In particular, given an $n$-node graph $G$ with girth $g\ge 3$, is there an example ...
1
vote
0answers
20 views

Finding locally and globally closing loops in a graph with toroidal topology

I have a two dimensional square lattice (with periodic boundary) with loops on it, i.e., collections of connected links which form closed loops. The lattice has the topology of a 2-torus and therefore ...
1
vote
0answers
27 views

How can I find the longest simple circuit in $K_n$? [duplicate]

How can I find the longest simple circuit in $K_n$? Is there a simple formula that exists?
1
vote
1answer
18 views

Can I make the following assumptions about the longest simple circuits?

The longest simple circuit in $W_n$ is $\frac{3}{2}n$ when $n$ is even and $\frac{3}{2}(n-1) + 1$ when $n$ is odd. I drew it out for a couple of graphs and it seemed to work. Can someone confirm ...
0
votes
0answers
19 views

Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)−d(v)?

This is MCQ of a competitive exam (GATE) , answer is option (d) given by GATE . I found explanation for (d) . With the commonsense or guessing the will be option (d) generally , I have doubt "Is given ...
0
votes
1answer
27 views

How do you find an odd hole in a graph?

Why is there no literature on finding odd holes in a general undirected graph? I found this paper that seems to enumerate ALL chordless cycles (http://arxiv.org/pdf/1309.1051v4.pdf) but apparently, I ...
0
votes
1answer
25 views

Bayesian network query

I am having a bit of trouble with something that I imagine is fairly easy. I am wondering how to get the probability of alarm, JohnCalls, and MaryCalls if they have no prior knowledge of their ...
0
votes
0answers
6 views

Example of weighted max cut taking exponential time iwth local search

In the Coursera algorithms course, the instructor mentions some graphs with weighted edges take exponential time to solve in the worst case with local search the max cut problem. The search algorithm ...
0
votes
0answers
19 views

What is the difference between tanner graph and factor graph?

Can someone please explain the difference between the factor graph and tanner graph in simple words? Is it possible to go from one to other? Moreover, are cluster graphs some simplified versions of ...
0
votes
1answer
23 views

Matching and greedy matching.

The problem is to prove that if $G$ has a perfect matching, then every greedy matching matches up at least half of the nodes. It is problem 10.4.4 y Lovász, Discrete mathematics. I do not understand ...
0
votes
0answers
21 views

How many subgraphs which have 4 vertices has a complete graph of 6 vertices?

$$K_6$$ How many subgraphs with 4 vertices has this graph? I was thinking $\binom{6}{4}12$
1
vote
0answers
38 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other.

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Provide ...
4
votes
1answer
75 views

How many words can be made with $7$ A's, $6$ B's, $5$ C's and $4$ D's with no consecutive equal letters.

I would like to know how many $22$ letter words can be made that have exactly $7$ A's, $6$ B's , $5$ C's and $4$ D's and have no consecutive letters the same. This problem is clearly equivalent to ...
0
votes
1answer
21 views

How many paths touch each node a given number of times?

How many paths of length $N$ through a complete graph pass a given number of times $k_n$ through each node $n$ ($\sum_n k_n = N$)?
0
votes
0answers
74 views

A simple question about rational numbers without a simple proof?

As in this question, study the quasigroup $(Q_+,/)$ of positive rational numbers under division. There are two obvious identities: $a/(b/c)=c/(b/a)$, for all $a,b,c\in Q_+$ $(a/b)/c=(a/c)/b$, for ...
1
vote
1answer
45 views

What is the minimum height of a binary tree with $n$ vertices?

What is the minimum height of a binary tree with $n$ vertices? Is it $$\lceil \log_2n\rceil$$, $$\lfloor \log_2{n} \rfloor$$ or $$\lceil \log_2{n+1} \rceil -1$$
0
votes
1answer
43 views

Proof that there isn't a graph search algorithm that is complete with finite memory

Is there a proof that any graph-search algorithm capable of exploring any graph (where there is a upper bound on the degree of each node and there is an ordering of the edges at each node-i.e left to ...
1
vote
0answers
20 views

What is the adjacency matrix of a squared (or k^th power) d-regular graph

If $A$ is the adjacency matrix of a $d$-regular graph, then I suppose $A'$(the adjacency matrix of the squared graph) should be $A^2 + A - dI$ (to remove self-loops). What about higher powers? How do ...
2
votes
1answer
43 views

Number of edges in the Hasse diagram for the $\subseteq$ relation on the set $\mathcal{P}\{1,2,…,n\}$

I am stucked at this problem: Let $G$ be the graph defined as the the Hasse diagram for the $\subseteq$ relation on the set $\mathcal{P}\{1,2,...,n\}$. ($n>0$) Determine how many edges ...
0
votes
0answers
27 views

Proof for maximum number of leaves in a tree with a given hopping distance

Hi I need help to prove the following for tree graphs which I believe is true: A tree with hopping distance $k$ (i.e. the most number of edges that any two vertices are apart) and n leaves either has ...
1
vote
1answer
21 views

Problem in understanding a notation in graph theory (intersection of edges)

On the French wikipedia, one can read: Soit un graphe simple non orienté $G = ( S, A )$ (où $S$ est l'ensemble des sommets et $A$ l'ensemble des arêtes, qui sont certaines paires de sommets), un ...
0
votes
2answers
73 views

Limit of an absorbing random walk. (Limit of power of real symmetric matrix)

I have a problem that comes from absorbing random walks on a connected undirected graph $G$ with two types of nodes, absorbing nodes and free nodes. We randomly pick a node to start, once the random ...
0
votes
1answer
35 views

Is it possible for a graph to have an Euler circuit and an Euler path?

Is it true that an Euler path should have two vertices of odd degree and an Euler circuit should have no vertices of odd degree? Is it therefore impossible to have a graph with both an Euler path and ...
4
votes
0answers
21 views

terminology for a “forward flow” type of random digraph

I am trying to find a characterization of the probability that vertex $1$ is connected to an arbitrary large vertex $N$ in a random digraph. The difference from typical random digraphs is that if ...
0
votes
2answers
46 views

Argument for the diameter of these 2 graphs…

I believe G1 has a diameter of 2 & G2 has a diameter of 4. However, is there a formal way to prove / argue for these given diameters? I'd like to see an argument without having to list all the ...
1
vote
0answers
53 views

Notation about commutative diagrams and their vertices

Usually vertices of a commutative diagram are labeled with objects like $A\overset{f}{\leftrightarrow} B$. But now I want to distinguish between vertices of the diagram even if they happen to ...
0
votes
0answers
19 views

For graphs in a recursive graph class: Does m = O(n) hold?

For recursive k-terminal Graph classes - for example definied in this paper - is it true that |E| = O(|V|)? If so, I would be very grateful for a reference! Thanks!
3
votes
1answer
31 views

Diameter of Schreier coset graphs.

I'm looking for a source from which to learn about Schreier coset graphs. Especially, examples in which combinatorial properties (specifically, diameter) of Schreier graphs are calculated. Also, is ...
3
votes
1answer
28 views

Prove that, for all $v\in\left(\mathbb E^3\right)^n$, $\langle Lv,v\rangle=\frac{1}{2}\sum_{i,j}^n a_{ij} \|v_i-v_j\|^2.$

Given a nonnegative, symmetric, $n\times n$ matrix $A$ the Laplacian $L$ of $A$ is defined to be $L=D-A$, where $D=\operatorname{diag}(d_1,\dots,d_n)$ and $d_l=\sum_{j=1}^n a_{lj}$. The Laplacian as ...
0
votes
1answer
56 views

Do graphs form groups under addition?

I just started studying graph theory, but according to the existence of the null graph and the definition of graph addition, they seem (non-directional graphs) to form a group. Is this true?
2
votes
0answers
76 views

Help to write a proof (category theory diagram)

It is known that $f$, $g$, $h$ are isomorphisms. It is known that $g\circ f = h^{-1}$. I need to write down the proof of the following theorem. I am an amateur mathematician and am not an expert in ...
1
vote
1answer
43 views

Maximizing colored vertices of a graph $G$ having less than $\chi(G)$ colors

Consider a $k$-partite graph $G$ of $N$ nodes and $q$ different colors with $q < k = \chi(G)$. I would like to determine how many vertices can I color at most with these $q$ colors. Consider the ...
1
vote
0answers
67 views

How do we prove commutativity of a diagram?

How do we prove commutativity of a diagram? There may be an infinite number of paths. We can't enumerate all paths.
4
votes
0answers
27 views

Lower bound for spectral gap for graph on $n$ vertices

Let $G = (V,E)$ be a graph on the vertex set $V$ with edges $E$. Let $A$ be the adjacency matrix for $G$ (so $A_{ij} = 1$ if vertices $v_i$ and $v_j$ are connected by an edge), and $D$ be the ...
1
vote
0answers
29 views

Adjacency matrix of a square of a graph.

What is the relation between $A(G)$ and $A(G^2)$? Where $G^2$ is the square of a graph $G$ and $A(G^2),A(G)$ their respective adjacency matrix.
0
votes
0answers
11 views

Smallest near triangulation of the plane with an external face of size $4$ for which all interior vertices have minimum degree $5$?

Consider the near-triangulation $G$ with an external face of size $4$. What is the minimum number of interior vertices for which G has minimum degree 5 as to those vertices? The degrees of the $4$ ...
0
votes
0answers
24 views

Graph Laplacians - self-study

I am self-studying graph laplacians in Kevin Murphy’s book “A probabilistic perspective on machine learning”. I understand that we introduce the vector f to proof that the matrix is positive ...
1
vote
0answers
23 views

factor graphs - example

I am self-studying graphs - and stumbled upon factor graphs - e.g. as described on https://en.wikipedia.org/wiki/Factor_graph. I have trouble concretizing what the factor vertices represent. Would ...
1
vote
1answer
35 views

In a bipartite graph $\alpha \beta \geq m$

That's basically it. $\alpha$ is the cardinality of the biggest independent set (no pair of vertices is connected) and $\beta$ is the cardinality of the smallest covering by vertices. I know this ...
3
votes
1answer
125 views

Construction of a Strongly Regular Graph which has regular Neighbourhood graphs in all iteration.

Notation and Definition: $G$ is a Strongly Regular Graph (not complete or a cycle) and is denoted by $\mathrm{SRG}(n,r, \lambda, \mu)$ if it has the following properties: Every two adjacent ...
11
votes
2answers
367 views

Minimum Cake Cutting for a Party

You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be ...