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
1answer
53 views

Infinite resistor problem from a graph theory standpoint

I am trying to understand the infinite grid of resistors problem from a graph theory stand point(classic xkcd/google problem). Since effective resistance is the same as the commute time, this is ...
0
votes
0answers
29 views
2
votes
2answers
32 views

Graph's Matching and edge covering

Let $G$ be a graph and $M$ a match with maximum size and $F$ an edge cover with minimal size. Prove that: $|M|+|F| = |V|$ That means that the number of all Matches with maximum size and the number of ...
1
vote
1answer
36 views

How many distinct directed acyclic graphs are there?

Given $|V|=4$ and $|E|=3$, how many distinct directed acyclic graphs can be formed? Isomorphic graphs should be counted as one. There is one where three periphery nodes point to a central node. ...
2
votes
0answers
50 views

proof of Triangle Removal Lemma

Where can I find a proof of the following version of Triangle Removal Lemma (or any version equal to it)? Let $G(V,E)$ be a graph on $n$ vertices such that it contains $\varepsilon n^3$ triangles, ...
3
votes
0answers
85 views

Integral identity graphs — smallest example

From Paulus Graphs. "The (25,2)-, (25,4)-, and (26,10)-Paulus graphs have the apparently rather unusual property of being both integral graphs (or asymmetric) and identity graphs (a graph spectrum ...
0
votes
0answers
54 views

Find the Eigenvalues of Petersen Graph

Petersen graph is k-regular graph on $n$ vertices and $m$ edges. We can find eigenvalue of $k-regular$ graph by characteristic polynomials of $G$ (denote $\chi_G (x)$) and $L(G)$ (denote $\chi_L (x)$)...
-1
votes
1answer
19 views

Adjacency matrix is totally unimodular

Prove that the adjacence matrix of a simple graph is totally unimodular... I know incidence matrices are totally unimodular because in every column there is a 1 and a -1... makes things easier. Any ...
6
votes
0answers
147 views

A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
2
votes
1answer
27 views

Finding a recurrence for number of paths in a certain tree

I have a graph which looks like this: The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is ...
3
votes
2answers
30 views

Metric dimesnion

Metric dimension of a graph $G$ can be defined as the minimal cardinality of the subsets $A\subseteq V(G)$ with the following property; For any two vertices $u$ and $v$, we are able to find a vertex $...
2
votes
0answers
34 views

Graphs derived from colorings of locally finite graphs

Let us assume we are in the following situation: We have a connected regular locally finite graph $G=(V,E)$ and let us call the degree of an arbitrary (and therefore any) vertex $d$. In addition we ...
0
votes
2answers
64 views

Finding the maximum length of a minimum spanning tree

Graph G has 4 vertices/nodes and 5 edges. It is also connected. Its edges have the following weights: 5, 8, 10, 16, 18. The minimum length for a minimum spanning tree of graph G would be ...
2
votes
0answers
32 views

Irregular self complementary graph.

Is there a family of irregular self complementary graph? Or are all self complementary graphs regular?
1
vote
1answer
47 views

What is the expected number of triangles contained in this graph?

I can't seem to understand this question and I really don't know where to start. Could someone please give an explanation as to how to go about answering this? A simple graph is formed randomly on ...
2
votes
2answers
24 views

Labelled spanning trees of $K_n-e$

Let $e$ be an edge of $K_n$- the complete graph on $n$ vertices. Prove that the number of labelled spanning trees of $K_n-e$ is $(n-2)n^{n-3}$. I think the answer lies in using some modified form of ...
-1
votes
0answers
70 views

Colouring a Tree

There are k different colors available. How many ways are there to color each vertex of the tree in one of the k colors such that for any pair of vertices having same color, all the vertices belonging ...
0
votes
0answers
14 views

Deduce Max flow min cut from Menger's theorem

I want to deduce the max flow min cut theorem from Menger's theorem, both on arc-connectivity in digraphs. Given a network with integer capacities c, one may replace each arc a by c(a) parallel arcs ...
5
votes
2answers
33 views

L(G) is isomorphic to G iff G is a cycle

The converse is pretty obvious. If G is a cycle, then it is isomorphic to it's line graph. How to prove that if L(G) is isomorphic to G, then G is a cycle...? P.S.- Assume G is connected
1
vote
1answer
72 views

If $G$ is a graph of order $n$ such that $\delta (G) ≥ (n-1)/2$ , then $\lambda(G) = \delta(G)$

Prove that if G is a graph of order n such that δ(G) ≥ (n-1)/2 , then λ(G) = δ(G). where δ(G)= minimum degree of the graph G λ(G)= minimum edge cuts to disconnect graph G κ(G)= minimum ...
1
vote
1answer
21 views

Eulerian path in directed graphs

I am a math student and am having trouble with the following problem. It would be nice if someone hand me some solution or at least some hint. Show that in a connected directed graph where every ...
0
votes
0answers
34 views

Probability mass function meeting the expectation of distributions of independent Bernoulli variables

Suppose there are $n$ objects that have probabilities $p_1, p_2, \ldots, p_n$ of being selected, respectively. The sum of these probabilities is not necessarily $1$. Also assume that the first $k < ...
0
votes
2answers
27 views

Calculate order of a graph from size of graph and size if its complementary.

Given the order of a graph (without loops) n, which size is 56. And its complementary graph which size is 80. How to find out the value of n?
3
votes
1answer
37 views

Uniqueness of graph neighbourhood sizes

I was thinking about graphs the other day, and had the following questions which I suppose fall under the topic of graph reconstruction. I am not very familiar with the literature, so in case this ...
0
votes
0answers
11 views

Corona of two graphs and Cartesian product of two graphs

I would like to know whether corona of two graphs is defined for two graphs with disjoint vertex set?? Also I would like to know whether Products of of two graphs (Cartesian, tensor,strong, ...
0
votes
0answers
23 views

Implicitization Problem on Graphs?

I learnt the implicitization problem for varieties in introduction course on Algebraic Geometry. I am trying to understand how to formulate a similar implicitization problem on graphs where the ...
1
vote
0answers
23 views

Arc-bases and Point-bases: when are they different for finite digraphs?

Definitions Given a digraph $D=(X,U)$, a point-basis of a digraph $D$ is a minimal vertex set from which a dipath exist to every vertex in $D$. An arc-basis is a minimal arc-reaching set. A subset ...
0
votes
1answer
42 views

Characterization of bicycle graphs

By "bicycle graph" I mean a minimal connected simple graph with at least two cycles. From Wikipedia: There are three possible types of bicycle: a theta graph has two vertices that are connected ...
0
votes
1answer
54 views

Non-trivial graph automorphism groups with $D_n$ as subgroup

I understand that the automorphism group of an $n$ cycle graph is the dihedral group $D_n$ of order $2 n$. From the comment of @Christian, I also understand that $S_n$ is the automorphism group of the ...
3
votes
0answers
87 views
+50

Maximal unit lengths in 3D with $n$ points.

Given $n$ points in 3D space (V), what is the maximal number of unit distance lengths (E) between those points? Here are a few possibilities. Some of them are chromatic spindles. ...
0
votes
1answer
30 views

A graph such that every set $S$ of vertices has at least $\frac32|S|$ neighbors, then $(\frac32)^{\frac{\text{diameter}-4}{2}}\leq n$

Let $G=(V,E)$ be a graph with $n$ vertices and with diameter $k$. Let $N(S)=\cup_{s \in S} N(s)$ denote the set of neighbors of $S \subseteq V$. Suppose that every set $S\subset V$ of size at most $\...
0
votes
0answers
24 views

suppose that $ r_{n} =(3, 3, 3, …, 3)$ ramsey number show $r_{n} \leq n(r_{n-1} - 1) +2$ [duplicate]

$r_{n}$ is ramsey number for $k_{1}, k_{2},..., k_{n}$ which it means the smallest size of a set which if we color all pairwise the element with n color we certainly could find a set of element with $...
0
votes
1answer
35 views

What is the necessary and suffices condition to build an r -regular graph?

I need to show what is necessary and suffices to have an r-regular graph with n vertices. where $n > r+1$ One way is to build that r-regular graph with n vertices ...
-1
votes
2answers
60 views

Is every finite category identifiable with a directed multigraph? (and vice versa?) [duplicate]

What seems implicit in this talk on youtube, is the claim that every directed multigraph (with loops) can be identified with a finite category and vice versa, if we consider the paths of the directed ...
1
vote
3answers
80 views

Is “Connected Component” unique for each graph?

Definition A connected component of an undirected graph $G$ is a subgraph where any two vertices are connected by paths. A connected component is a maximal connected subgraph in $G$. Consider a ...
2
votes
1answer
56 views

Show that for each of the following graphs G there exists up to isomorphism precisely one category A with G(A) = G.

I was working through the exercises in Abstract and Concrete Categories: The Joy of Cats (http://katmat.math.uni-bremen.de/acc/acc.pdf) and I was stuck on exercise 3A.(d). It seems to me that the ...
1
vote
1answer
91 views

Eigenvalues of periodic lattice Laplacian?

Consider the graph given by taking a rectangular lattice with $m$ rows and $n$ columns and joining each vertex to its four nearest neighbors, where vertices on the boundary are connected periodically (...
2
votes
1answer
33 views

Minimal alpha-Spanning Tree

I got a really strange question with a definition that I've never seen before, so I hope someone of you can help me with it: Let $G = (V,E)$ be a connected graph and $\alpha \in \mathbb{R}$. A graph $...
0
votes
0answers
45 views

Strategy of ball math game

Found math game: http://www.emathhelp.net/math-games-and-logic-puzzles/rgbw/ What is a strategy for it? I can make 15 white balls max. Any thoughts?
5
votes
0answers
120 views

Points with power distances

It's possible for seven points to be at integral distances. I'm dallying with powered triangles, though, so I'm looking for point sets where all distances are powers of a fixed $x$ value. For example,...
1
vote
0answers
26 views

Notation for directed and undirected edges of a graph

Let $G$ be a directed graph. I want a way to talk about the edges of $G$ without orientation, so I defined a function $u$ for "unorient" which takes $G=(V,E)$ to $u(G)=(V,E')$ where $$E'=\{\{v,w\} \...
4
votes
2answers
43 views

Hall's marriage thereom with max-flow-min-cut

I heard that Hall's marriage theorem can be proved by the max-flow-min-cut theorem. Could you outline how that is possible? Hall's theorem says that in a bipartite graph there exists a complete ...
1
vote
1answer
20 views

Ford-Fulkerson for irrational capacities

We know that the Ford-Fulkerson algorithm works for integer capactities but it may loop forever for irrational ones. Is there an algorithm that only alters Ford-Fulkerson slightly but works for ...
0
votes
0answers
8 views

Gallai's implication's for bipartite graphs

I have this exam question: What are the implications (or what is an alternative form) of Gallai's theorem for bipartite graphs. I have been thinking for some time but couldn't come up with anything, ...
0
votes
0answers
38 views

Encoding a graph coloring problem in SAT/CNF for DPLL algorithm

I'm having trouble trying to convert the following problem to SAT for later application to DPLL: Given a connected, undirected graph G, with k colors $\{ c_1 , ..., c_k \} $ and any number of ...
0
votes
0answers
16 views

give an example of r-regular graph that $k(G)\neq k'(G)$

where $k(G)$ is the number of minimum set of vertices in $G$ whose deletion from a graph $G$ disconnects it. and $k'(G)$ is the number of minimun set of edges in G whose deletion from a graph $G$ ...
0
votes
0answers
23 views

Number of graphs which have $m$ connected components in all subgraphs obtained from the complete labeled graph $K_n$ by removing zero or more edges.

Let $Ans_m$ be the number of graphs which have $m$ connected components in all subgraphs obtained from the complete labeled graph $K_n$ by removing zero or more edges. Then we get $\sum_{m}Ans_m$ in ...
0
votes
0answers
12 views

Gilmore-Hoffman characterisation of comparability graphs

Gilmore and Hoffman's characterisation of comparability graphs says that: "$G$ is a comparability graph precisely if whenever $v_1v_2...v_r$ forms a cycle in $G$, such that no $v_i$ and $v_{i+2}$ ...
0
votes
1answer
25 views

Proof of Baranyai's theorem

Could you give me a full proof of Baranyai's theorem. I looked at a lot of sites but they seem to only give partial proofs. I read that Schrivjer proved it using the max-flow-min-cut theorem but I can'...
1
vote
1answer
70 views

Complete Graph with odd degree

It is known that the Complete Graph $K_n$ has $n^{n-2}$ spanning trees. The $K_{10}$ has $10^8$ spanning Trees. Now my question: How can I compute the number of spanning Trees with odd degree of its ...