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

4
votes
1answer
245 views

In the marriage problem, if each girl knows at least $m$ boys, then there are at least $m!$ ways to arrange the marriages.

I'm finding problems concerning Hall's theorem very difficult even when they're not. (See here for example. I'm sure I wouldn't have come up with the solution in a million years even though it's ...
1
vote
2answers
545 views

What is the expected size of the largest strongly connected component of a graph?

Given a directed graph with n vertices and the probability of any edge existing being p, what is the size of the largest strongly connected component in the graph? What if its undirected graph? Can we ...
20
votes
3answers
884 views

Exceptional books on real world applications of graph theory.

What are some exceptional graph theory books geared explicitly towards real-world applications? I would be interested in both general books on the subject (essentially surveys of applied graph ...
2
votes
0answers
42 views

defining relationship between geometric entities (features)

I have different features located on a plane (2D); I want to define this structure mathematically in a way to represent their relations. Some of features are aligned in horizontally, vertically or ...
2
votes
1answer
92 views

The marriage problem with the constraint that a particular boy has to find a wife.

Here I'm considering the version of the marriage problem in which there can be more boys than girls. Suppose there are two sets, one of boys and one of girls, the two satisfying Hall's condition for ...
0
votes
0answers
38 views

composition of graphs while eliminating inner edges

I am having left side sub graphs and want to compose each after the other. my objective is to get the right side graph. question 1: can any one suggest me a way to do this. (Note: I am having ...
3
votes
1answer
889 views

Is there a formula for finding the number of nonisomorphic simple graphs that have n nodes?

As my subject line asks, is there a formula for finding the number of nonisomorphic simple graphs there are with n nodes, outside of trial, error, and enumeration over max degrees of vertices? Thanks ...
0
votes
1answer
108 views

Maximum number of elements, where no two are in relation

I have a set S. I have reflexive, symmetric and non-transitive relation R on SxS. I have to find size of set P, which is the biggest subset of S where : Any two distinct elements of P are not in ...
1
vote
0answers
32 views

finding the decomposition of Laplacian matrix with position of zero elements unchanged

I'd like to know whether it's possible to find the decomposition of a Lapalacian matrix $A$ $B^TB = A$ where $B$ has the same dimension with $A$ and the position of zero elements in $B$ is the same ...
0
votes
1answer
163 views

Basic Graph Theory on degree sequences.

Here is a tricky one. In a graph with 8 vertices, seven have degrees 1, 2, 3, 4, 5, 6 and 7. Find the degree of $8^{th}$ vertex? The question further asks about its chromatic number?
2
votes
1answer
39 views

Isomorphic graphs + alpha

Which of the following graphs are isomorphic ? I. 4 vertices A,B,C and D are positioned to form a square with side AD missing. i.e, AB,BC and CD are the sides and they are perpendicular. II. 4 ...
3
votes
0answers
102 views

Mathematical notation for formulas involving trees

I am working on document that requires me to write such things as "$T_1$ is a descendant of $T_0$", or "$N_1$ is an parent of $N_2$". For now, I've been highjacking set notation for use in formulas, ...
6
votes
3answers
471 views

Number of pairs of points whose distance is one

Let $S$ be a set of $n$ points in the plane, the distance between any two of which is at most one. Show that there are at most $n$ pairs of points of $S$ at distance exactly one. My attempt on ...
1
vote
1answer
124 views

Tournament where any k players are beaten by another

In a tournament every player competes against each other. Every match has a winner. A tournament has property $P_k$ if for every set $S$ of $k$ players there exists a player $a\notin S$ who beats ...
2
votes
1answer
132 views

how to write the process of decomposition of a graph into shortest closed sub graphs

If I want to decompose a graph in to possible shortest closed cycles (as shown in right side). then how can i describe this process with mathematical notations. to understand please refer below ...
3
votes
1answer
77 views

How to effectively detect negative cycles in graph?

I proposed to check the edge weighs and then run shortest path and check if the shortest path weight is not going to $-\infty$. Any better ideas?
1
vote
1answer
288 views

What types of questions is graph theory best suited at answering?

I'm dealing with a particular optimization problem at work (financial scorecards), and I noticed that my dataset can be set up as a set of DAGs, where the scorecards for each customer comprise a ...
3
votes
1answer
220 views

Dijkstra's algorithm does not work?

I mean Dijkstra's algorithm for the shortest path. Sorry for noob question. In all descriptions that I saw (including wikipedia), on every step, it always selects the nearest neighbor based on ...
0
votes
1answer
268 views

Mathematical notation of graph subdivision

If anyone can define a directed graph subdivision with mathematical notation, please post a response. My second question is: Irrespective from the planar embedded graph or not, is this definition ...
3
votes
1answer
445 views

Diameter of $k$-regular graph

Given a $k$-regular graph, its diameter is bounded by $O(n/k)$ where $n$ is the number of nodes and $k$ is the degree of each node. Is there any straight-forward way to prove this result?
4
votes
2answers
88 views

Ambiguity in the definition of graph homomorphism

Given graph $G$ and $H$ and a function between $f : G \rightarrow H$ between the vertex sets, we say that $f$ is a graph homomorphism iff for all vertexes $x$ and $y$ of $G$ such that $xy$ is an edge ...
1
vote
1answer
550 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
1
vote
1answer
40 views

Infinite non-self-intersecting paths in graphs

Let $G$ be a graph (of any cardinality). Suppose all its vertices have finite degree. Then does there exist an infinite non-self-intersecting path of an infinite sequence of vertices in $G$? If ...
3
votes
2answers
67 views

Graphs with zero spectrum / nilpotent symmetric matrices

Is there a graph theoretic characterization of those graphs with zero spectrum? Alternatively, can one at least characterize all symmetric nilpotent (complex) matrices, so that one could recognize ...
2
votes
2answers
352 views

Prove that a strongly connected digraph has an irreducible adjacency matrix?

In our homework we are asked to prove the above fact. If anybody would be willing to give advice I would be most thankful. Thanks
1
vote
1answer
90 views

Prove $MM^t=A+kI$ for matrices associated to graphs

How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices? It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), ...
1
vote
1answer
67 views

Decomposing a Connected Graph into Walks

Problem: Assume G = (V,E) is a connected graph with 4 vertices of odd degree. Show G can be decomposed into 2 edge-disjoint simple (no edge is repeated) walks. Attempt at a Solution: Suppose the four ...
1
vote
1answer
61 views

Ambigous line graph definition

While reading the openbook "Algorithmic Graph Theory " I came by Definition 1.7 which is supposed to define what a line graph is , here is the definition: Definition 1.7. Let $G=(V,E,h)$ be an ...
2
votes
1answer
449 views

What are the number of 4 cycles in the Complete Bipartite graph?

The question I have is: How many cycles of Length 4 are there in a Complete Bipartite graph in $K_{n,n}$? I can see there is 1 distinct cycle in $K_{2,2}$ but after that I can't seem to get it ...
0
votes
1answer
89 views

Calculating number of connected graphs

I want to calculate the number of connected graphs with n vertices. There is no other constraints like loop etc. I am unable to think a general method for the ...
1
vote
1answer
54 views

What is the graph $K^c_m$?

The book "Graph Theory with applications" by J.A. Bondy and U.S.R. Murty, which is available here. The Theorem $4.6$ of this book says that: If $G$ is a non-Hamiltonian simple graph with $n≥3$ ...
2
votes
1answer
697 views

How to show a graph is not Hamiltonian?

Suppose you are given a graph $G$ with the properties that $G$ is 3-regular, $v_G = 10$ where $v_G$ is the number of vertices in $G$, and girth$(G) \geq 5$. How can you tell that $G$ is not ...
2
votes
3answers
769 views

Graph with degree sequence (3,3,3,3,3,3)

Does there exist a graph with degree sequence (3,3,3,3,3,3)? I am pretty such graph does not exist since I have tried to draw one without success, but is there a way to prove it?
1
vote
1answer
340 views

Breadth-first search tree

It seems intuitive, and is actually proven in many books, that each path from starting vertex to another one in any search tree of a breadth-first algorithm is the shortest. However, I couldn't find ...
0
votes
1answer
154 views

Veblen's theorem for digraphs

Here is another problem from Bondy/Murty: Prove that A directed graph admits a decomposition into directed cycles if and only if it is even. Here a directed graph is even if all its vertices ...
3
votes
2answers
230 views

Eccentricity of vertices in a regular graph

I was just trying to find out the eccentricity of the vertices in regular graphs, given in the link http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG. Surprisingly, eccentricity is the same ...
9
votes
1answer
518 views

Petersen graph is not a Cayley graph

How can I show that the Petersen graph is not a Cayley graph? I don't know very much about Cayley graphs, I know that they are vertex-transitive, but so is the Petersen graph. It probably has to do ...
1
vote
1answer
108 views

Graph chromatic number proof

How can i prove this? Show proof that for any edge $e$ of graph $G$ we have $\chi(G-e)\leq\chi(G)\leq\chi(G-e)+1$. Give examples showing that the inequalities are sharp.
1
vote
1answer
283 views

Adjacency matrix defines a distance metric

Let $A$ be adjacency matrix of a graph (perhaps weighted). Prove that \begin{equation} \sum_i \sum_j A_{ij} (f_i- f_j)^2 = \mathbf{f}^T L \mathbf{f} \end{equation} where $\mathbf{f}$ holds values of ...
2
votes
3answers
135 views

Drawing graphs (vertices and edges) with or without technology

Given a collection of vertices $V$ and a collection of edges $E \subseteq V\times V$, is there an algorithm or program that will allow you to draw a nice graph? The placing of the vertices is very ...
4
votes
1answer
205 views

Graph coloring (chromatic number) proof

How can i prove this? If a graph $G$ is countable and if $a \in \mathbb{N}$, then $\chi(G) \leqslant a$ if and only if $\chi(S) \leqslant a$ for every finite subgraph $S$.
13
votes
2answers
182 views

Representation theorems for groups

There are two baffling representation theorems for groups: Every group is isomorphic to the automorphism group of some graph. (see Frucht's theorem) Every group is isomorphic to the fundamental ...
1
vote
0answers
108 views

Matching Endpoints of Bipartite Graph

I am trying to work out this problem: Suppose that $G=(V,E)$ is a bipartite graph with bipartition $(V_1, V_2)$ and that $A \subseteq V_1$. Show that the maximum number of vertices of $V_1$ that ...
0
votes
1answer
206 views

Let T be a tree with sub-trees which each set has a vertex in common - hence T has a vertex in all of its sub-trees?

The question is: Let T be a tree with sub-trees $T_1,T_2,..,T_n$ such that all trees $T_i,T_j$ have a vertex in common which each set has a vertex in common - show that T has a vertex in all $T_i$. ...
0
votes
1answer
162 views

edge-disjoint simple walks

Let $T$ be a tree on $v$ vertices, $v$ greater than $5$, with precisely four vertices of degree $1$ each and precisely one vertex of degree $4$. Find the degrees of the remaining vertices of $T$, and ...
-1
votes
2answers
630 views

Determine all isomorphism classes of trees on six vertices

how can I determine all isomomorphism classes of trees on six vertices?
0
votes
0answers
113 views

Nilpotency of the adjacency matrix of a directed tree network

Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and ...
2
votes
1answer
108 views

Bounding minimal cover with maximal matching in connected graph

Let $G=\left(V,E\right)$ be a connected graph where $\left|V\right|\,\mbox{mod}\,2\equiv0$. Denote $\nu$ to be $G$'s maximal matching (a set of disjoint edges) size and $\tau$ to be $G$'s minimal ...
2
votes
1answer
487 views

Friendship paradox demonstration

I should demonstrate the friendship paradox using the graph theory in this way: The social network graph is represented by an adjacency matrix $a_{ij}$ ($m$ is the number of edges, $n$ is the number ...
4
votes
2answers
103 views

The Dinitz problem

I would like to ask if someone knows about good books or online articles about The Dinitz problem or maybe someone can explain the problem a little. Consider $n^2$ cells arranged in an $( n \times ...