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
178 views

Finding the number of 5-node labeled connected graphs via generating functions

Problem: Find the number of ways to connect a graph having 5 labeled nodes so that each node is reachable from every other node. I have solved this problem using principle of inclusion and exclusion ...
0
votes
0answers
269 views

Using maximum flow algorithm to check existence of a matrix

Using the maximum flow algorithm, I have to determine if there exists a $3\times 3$ matrix $P$ (such that all elements are $\geq 0$). I'm given: The maximum values of the row sums The column sums ...
2
votes
0answers
52 views

Crossing number of simple undirected graph

There's a well-established result which provides a lower bound for the crossing number of any simple undirected graph. However, is there any known result for an upper bound in this setting?
1
vote
1answer
77 views

Calculating a minimum connected subgraph containing a fixed set.

Let $(V,E)$ be a connected, planar graph, and let $S \subset V$ be some desired set of vertices. What is the fastest algorithm, if it exists, to calculate a connected subgraph of $(V,E)$ which ...
0
votes
1answer
219 views

Graph theory (Chromatic Polynomial)

What is chromatic polynomial of tree? What is chromatic polynomial of complete graph with n vertices? Sketch two different (i.e, nonisomorphic) graphs that have the same chromatic polynomial.
2
votes
1answer
160 views

Unions of matchings in a bipartite graph

Question: Let $G$ be a bipartite graph with colour classes $X$ and $Y$. Assume there are two matchings in $G$: $M_1$ which covers $X' \subset X$, and $M_2$ which covers $Y' \subset Y$. Prove that ...
0
votes
1answer
32 views

Partitioning an interval graph into matchings

Consider $C$, a family of intervals on $R$, such that each $p ∈ R$ is contained in at most $m$ of these intervals. Prove that there is a partition of $C$ into $m$ classes $C_1, ..., C_m$ so that each ...
2
votes
1answer
199 views

Properties of Petersen graph

Petersen graph is graph with 10 vertices and 15 edges What is domination number and independence number of Petersen graph?
-1
votes
1answer
134 views

Interesting question on Graph Theory

In a village there are an equal number of boys and girls of marriageable age. Each boy dates a certain number of girls and each girl dates a certain number of boys. Under what condition is it possible ...
0
votes
1answer
180 views

Prove trees has a leaf in set of vertices coloured black, or set of vertices coloured white

Prove that every tree has a leaf in the set of vertices coloured black, or the set of vertices coloured white, whichever has the larger cardinality (or both if they have equal size). Any hints?? ...
1
vote
1answer
296 views

Proving a simple graph is a connected graph

Does any proof exist that a simple graph with $n$ vertices such that the least vertex degree is $\geq \frac{n-1}{2}$ is a connected graph? (i.e. does such a proof have a name?)
1
vote
2answers
537 views

Constructing a 3-regular graph with no 3-cycles

I have a question that is as follows: For each integer $n \geq 3$, construct a 3-regular graph on $2n$ vertices such that $G_n$ does not have any 3-cycles. Here is what I have: I have $2n$ ...
3
votes
1answer
68 views

What is the name of graph problem that ask to select some vertices to see every edges.

I want to place light bulbs on some vertices (each bulb will lit up every edges it connected) where all edges lit up. e.g. suppose I have this simple planar graph, Sufficient vertices to place ...
2
votes
0answers
188 views

Low-rank approximation to the Graph Laplacian matrix of a regular grid.

As mentioned in the title, does anybody know any methods of efficient low-rank approximation $LL^T$ to the Graph Laplacian matrix $A$ corresponding to a square lattice? (except PCA)
0
votes
1answer
43 views

Operation on Elements of Edge Space

I try to figure out the strange operation on two element $F$ and $F'$ of the edge space. The operation was introduced in textbook Graph Theory by Diestel. Given two elements $F, F'$ of the edge ...
1
vote
2answers
166 views

Theorem of Eulerian Path

I am a little bit confused by the proof of Theorem 1.8.1 (Euler 1736) on the page 23 of the textbook Graph Theory by Diestel. Theorem 1.8.1 (Euler 1736) A connected graph is Eulerian if and only if ...
0
votes
1answer
40 views

Directed and Undirected Hyperedge

I am trying to define an API for manipulating graphs and hypergraphs. Does it make sense to talk about directed and undirected hyperedges in an hypergraph? Can we talk about successors and ...
4
votes
1answer
168 views

What is the difference between first and second right eigenvectors of a row stochastic matrix and their meaning?

In an $n\times n$ non negative row stochastic matrix (rows sum up to 1). The entries of the stochastic matrix I have represent directed links between countries. Why is the first right eigenvector a ...
3
votes
0answers
70 views

Define composition of small cyles and making a big graph

I am having following sub graphs and wish to compose all and make a one bigger graph (say G). After that, I want to select the closed path where it is passing along the outer vertices of that ...
1
vote
0answers
48 views

Mean matching size

Suppose there is a simple bipartite graph $G(X,E,Y)$, where $|X|=n_1$, $|Y|=n_2$, $|E|=m$. The edges $E$ are chosen uniformly at random. The question is what is a mean value of the size of the ...
2
votes
1answer
77 views

Diameter of graph is $\geq 4$

Let $G$ be any graph such that $\Delta G=k\geq2$. If there are at least $k^3-k^2+k+2$ vertices, show that $\operatorname{diam}(G)\geq 4$. Can any one give idea on how to approach this problem
0
votes
1answer
147 views

Hasse diagram with maximal chain not counted in maximal anti-chain

Construct a post (Hasse diagram) that contains a maximal anti-chain of size $r$ and, after removing a chain $C$ of maximal size, it still contains an anti-chain of size $r$.
1
vote
2answers
673 views

Discrete math: Euler cycle or Euler tour/path?

Could someone help explain to me how I can figure out if the graphs given are Euler cycle or Euler path? Is it through trial and error? Here are some examples: Would appreciate any help.
4
votes
1answer
75 views

Points on a plane

I have been assigned this problem and am not sure how to approach it! Please help me figure out what I should do! Let $S$ be a finite set of points in a plane chosen to have the property that for ...
3
votes
1answer
109 views

Prong Corollary, $G$ has a subgraph isomorphic to $T$

There is a corollary in Diestel textbook Graph Theory. Corollary 1.5.4. if $T$ is a tree and $G$ is any graph with $\delta(G) \geq |T|-1$, then $T \subseteq G$, i.e. $G$ has a subgraph isomorphic ...
5
votes
3answers
64 views

Adding edges to a forest from another forest in the same graph

I am having problems with this question: Let $G = (V,E)$ be a graph. Let $F$ and $F'$ be forests in $G$ such that $|F|< |F'|$ (where $|F|$ indicates the number of edges of $F$). Show that there is ...
1
vote
3answers
57 views

Graph of a matrix and a positive power for the the matrix

A graph has a path from node $j$ to node $i$ if and only if its adjacency matrix has a positive element $(i,j)$ of $A^k$ for some integer $k.$ A proof for this statement will be highly appreciated.
2
votes
2answers
148 views

What is a Ramsey Graph?

What is a ramsey graph and What is its relation to RamseyTheorem? In Ramsey Theorem: for a pairs of parameters (r,b) there exists an n such that for every (edge-)coloring of the complete graph on n ...
0
votes
0answers
77 views

disjoint and inverse domination

The disjoint domination number $\gamma\gamma(G)$ is defined as $$\gamma\gamma(G)= \min\{|S_1| + |S_2| : S_1\text{ and }S_2\text{ are disjoint dominating sets of }G\}.$$ Just want to verify if this ...
3
votes
0answers
228 views

A graph has k edge-disjoint perfect matchings. minimum number of edges?

Let $n\ge 2$ be an even number and $0<k<n$ be an integer. What is the smallest number $x$ satisfying the following: If a simple graph with $n$ vertices has at least $x$ edges then it contains ...
2
votes
1answer
53 views

Can expressing there is an edge that connects two vertexes be expressed using only first-order logic?

Suppose that we want to express "there exists two vertexes that can be shown to be connected by an edge." in first-order logic. Can this statement be expressed using only first-order logic? Or does ...
1
vote
2answers
80 views

Some questions on toroidal graphs

The complete graph $K_4$ is planar, and like every planar graph it is also embeddable into the torus. a) Why does $K_4$ count as a triangulation of the sphere, but not of the torus? b) What's the ...
0
votes
0answers
27 views

Second-Order Random Choice Proof

Given $G = (V,E)$ ;$ |V| = n, |E| = m$ then choose $T$ with $t$ vertices uniformly I have to proof the graph theory as $$E[X] - E[Y] \geq a$$ Which $$E[X] \geq \frac{(2m)^t}{n^{2t-1}}$$ X is random ...
1
vote
1answer
757 views

A graph $G$ is bipartite if and only if $G$ can be coloured with 2 colours

I've been stuck on this question for some time, can anyone please help me out with it... Definition: A graph $G = (V, E)$ can be coloured with $k$ colours if $\forall v \in V$, $v$ is assigned ...
2
votes
1answer
109 views

Kuratowski theorem in Möbius band

I was curious to know where the theorem is failing (a graph is planar iff it doesn't contain subgraphs isomorphic to $K_{3,3}$ or $K_5$) Obviously, the theorem fails if we're in a Möbius band, as it ...
0
votes
2answers
571 views

Relation Between Girth and Diameter of $G$

I have difficulties in understanding the proof for the following theorem. Theorem. Every graph $G$ containing a cycle satisfies $\def\diam{\operatorname{diam}}g(G) \leq 2\diam(G)+1$. Q:The first ...
0
votes
2answers
768 views

Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle

When proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle, is it sufficient to just remove that edge that created a cycle, then it ...
0
votes
1answer
197 views

Different formulation of a Traveling Salesman Problem

Given a undirected, weighted, complete graph $(V,E,c)$ with $c \to \mathbb{N}$ and $v_0 \in V$ we are looking for a set $E' \subset E$ minimal with respect to $c$ with the following conditions: for ...
3
votes
3answers
116 views

G is connected, but is not connected if any single edge is removed from G. $\implies$ Any two vertices in G can be connected by a unique simple path.

How does how show the following implication to be true: G is connected, but is not connected if any single edge is removed from G. $\implies$ Any two vertices in G can be connected by a unique simple ...
0
votes
3answers
831 views

Show that in every (not necessarily connected) graph there is a path from every vertex u of odd degree to some other vertex v…

Show that in every (not necessarily connected) graph there is a path from every vertex $u$ of odd degree to some other vertex $v$ ($u \neq v$), also of odd degree.
4
votes
0answers
78 views

Sequences of Integers such that no one divides the product of two others.

I'm working on of a problem of Bollobas' Modern Graph Theory, but I can't seem to get the last part of the problem: Let $1<a_1<a_2< \cdots a_k \leq x$ be natural numbers. Suppose no $a_i$ ...
2
votes
1answer
132 views

Graph Theory Number of 4 cliques from 10 3 cliques

I am try to find a rigorous way to prove that given a graph that has exactly 10 3 cliques(triangles), the maximum number of 4 cliques that can be formed is 3. Or more generally if there is connection ...
2
votes
2answers
77 views

How to find index of ordered pair

Suppose i have an undirected graph with V vertices, i need to store somehow flags for all possible edges, for now i have chosen bit-array of length $\tbinom n2$. So, question is, how to find index ...
3
votes
1answer
98 views

to check a property of square of a graph

I am trying to work out a problem. Given a self-centered graph, is the square of the graph also a self-centered graph? I tried numerically on few graphs given in ...
1
vote
3answers
141 views

Adjacency graph of cutting plane is a bipartite graph

Each time you draw a line on a plane, you are cutting it in half. Suppose you keep doing this without drawing a line parallel to a previous one. An adjacency graph can be constructed to represent this ...
4
votes
1answer
54 views

graph theory, geometry

I have some box with dimensions x,y,z. I put a net around it which includes the top and bottom. The net has unit squares on it. Whats the maximum amount of cuts you can make on the net but still have ...
0
votes
1answer
134 views

Shortest acyclical path between two nodes, negative weights allowed

I have the following (directed, edge-weighted) graph problem. In a set of n vertices, G, there is a source vertex, s. I need to compute the shortest path between s and every other vertex. I can't ...
3
votes
1answer
150 views

Lowest degree of a coefficient in a chromatic polynomial for a simple connected graph

Ok so I know a chromatic polynomial can't ever have a constant term, but why is the lowest degree of a coefficient in a chromatic polynomial for a simple connected graph always 1? Is there a simple ...
1
vote
0answers
65 views

How to make this inference: Degree of a node in a graph is significantly diffenrent from poisson distribution

I am working on Gene-Gene interaction graphs. I build a graph by adding edges between genes (nodes) which show statistical interaction in predicting a quantitative parameter value (say, brain volume) ...
1
vote
0answers
529 views

Proving Vizing's Theorem using Induction

So I would like to prove Vizing's theorem (let d be the maximum degree of any vertex in graph G, any graph can be edge-colored with d or d+1 colors) using induction on the edges of G...here's my ...