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
2answers
48 views

Right way of getting degrees of vertices

Suppose I have the following list of nodes: A E G A E H A F G A F H B E G B E H B F G B F H C F C E D G D H Every line indicates the connections between those nodes. So there is a connection ...
0
votes
1answer
54 views

Number of paths in hypercube graph

I have seen that the number of node-disjoint, shortest paths (between two vertices) from x to y in hypercube graph is d(x,y). I was wondering is there a way to find and prove the formula for: 1) ...
0
votes
1answer
23 views

Euler's formula about graphs embedded in $\mathbb{R^2}$

State and prove Euler's formula about graphs embedded into $\mathbb{R^2}$ I know that if we suppose $ G $ is a finite connected graph drawn on the surface of a sphere $ S^2 $. Then the ...
0
votes
0answers
16 views

The modularity formula of Newmann and Girvan

I have question concerning the modularity formula of Michelle Girvan and Mark Newman. It says that it measures the fraction of edges in a network, that connects nodes, within the same ...
0
votes
0answers
22 views

Directed Weighted Graph with no cycles - LP

I have directed weighted graph. I have to find a set of edges with minimal sum of their weights that without the set graph becomes acyclic. I can call lp solver multiple times. I'm kind off lost on ...
-4
votes
1answer
69 views

First scientific work. [closed]

One year ago I decided to myself to write my own scientific work in number theory, graph theory or combinatorics. I tried to find the teacher and theme during this year, but unfortunately I didn't ...
0
votes
0answers
9 views

Multi modal transport network and graph theory

I am attempting to model a multi layered transport graph with points that allow for travellers to laterally transfer between graphs, in order to make use of different transport nodes. Conceptually, ...
0
votes
1answer
26 views

Graph theory notation misunderstanding

I know $K_n$ means the complete graph on n vertices. But in my lecture notes it said "Consider $2K_n$. Please could you tell me what this means?
1
vote
1answer
27 views

Calculate the number of SDR's in $A_i:=\{1,\dots,n\}\setminus\{i\}$

Suppose that $A_1,A_2,\dots,A_n$ are sets, which we refer to as a set system. A (complete) system of distinct representatives is a set $\{x_1,x_2,\ldots,x_n\}$ such that $x_i \in A_i$ for all $i$, and ...
0
votes
0answers
12 views

$\epsilon$-regular bipartite class

Suppose that $G$ is a bipartite graph, with vertex classes $V_1$ and $V_2$ each of size $n$ and the maximum degree of $G$ is at most $\epsilon^2n$. Then show $(V_1, V_2)$ is $\epsilon$-regular in $G$. ...
0
votes
0answers
15 views

Minimum number of $m \times m$ matrices needed to recover a single large matrix

This problem was motivated by the need to efficiently train a neural net on a dataset in which the labels represent dependencies between examples, but nothing about it is machine-learning specific so ...
6
votes
3answers
211 views

Is there any algorithm to find Isomorphism function between two graphs?

Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a ...
1
vote
1answer
32 views

Definition of Perfect Elimination Ordering?

The answer to this question could be trivial ! Definition: According to the wikipedia page: A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each ...
1
vote
1answer
23 views

How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph?

How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph? Say I have a graph with chromatic number $k$. How do I prove that the chromatic number any ...
0
votes
0answers
13 views

Finding a circuit in a weighted graph with weight closest to desired value

In an edge-weighted graph, is there an algorithm to find a circuit starting from a certain vertex, where the sum of the weights on the circuit is closest to a desired value? For instance, say I want ...
0
votes
1answer
63 views

Counting edges in a finite connected graph where each vertex is exactly one of two values.

Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ ...
2
votes
0answers
48 views

The Crossing Number of a family of graphs which contain the complete bipartite graphs.

Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ ...
1
vote
1answer
87 views

Chess kings number of arrangements

How to find $2500$ chess kings number of arrangements on board $100\times100$? Is it possible to do that with just combinatorics? Will it be less then $(51^{50}\times2^{2500})$ and $(51^{100})$
0
votes
0answers
21 views

Does bipartite graph that $|X|=|Y|=n$ and $d(G)\ge \frac n2$ ; has complete matching?

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets and (that is, and are each independent sets) such that every edge connects a vertex in to one in . And ...
0
votes
0answers
13 views

Existence of some well known family of generalized graphs

I am in interested to know about some well known family of generalized graphs. Till now, I am aware of only one generalized family of graphs : Generalized Petersen graphs. Is Generalised quadrangles ...
1
vote
1answer
61 views

Is the category of simple graphs finitely complete?

I have read (on nLab and wikipedia) three conflicting statements: The category of simple graphs is finitely complete The category of simple graphs has no terminal object A category is finitely ...
0
votes
0answers
7 views

Prove that chromatic number of a graph is less than the chromatic number of its Hajos graph.

Prove that $\chi (G) <= \chi (H (G,v_1,v_2)) <= \chi (G-v_1v_2) + 1$, where $H (G)$ is the Hajos graph of g.
3
votes
0answers
24 views

Diametrl path of a graph

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this: ...
0
votes
0answers
18 views

Domain of Injectivity of Analytic Map

Suppose we have an analytic map $f: \mathbb{D} \to \mathbb{C}$. Then the set of points where the function is not locally injective is a discrete set. Suppose first for simplicity that the points ...
0
votes
1answer
37 views

Is this dual transform incidence and order preserving?

I am trying to understand duality explained in the book Computational Geometry Algorithms and Applications, 3rd Ed - de Berg et al. Unfortunately, I have some problem of solving a question in this ...
0
votes
1answer
41 views

Clique number of the Hajos Construction of a Graph

Prove that $\omega(G)-1 \leq \omega(H(G,v_1,v_2)) \leq \omega(G) $. The $H(G,v1,v2)$ indicates the Hajos Construction of a graph. I can prove this for $K_n$ but I have no idea how to generalize for ...
0
votes
0answers
14 views

How do you find the expected Cover Time of a graph?

I can only find resources that give an upper bound on the cover time, but not how to find the exact expected cover time of a graph. Somebody told me it's related to the coupon collector problem, but I ...
0
votes
0answers
11 views

What condition can I impose on a graph to know the properties of certain subsets

I am sorry for the question being a bit open. I ran into this definition while working on a non graph theoretic problem. I am not a graph theorist myself and I have no idea how to look it up. Any ...
0
votes
2answers
38 views

Proving the number of leaves of a tree. (Graph Theory)

Prove that if a tree has $n$ vertices (Where $n\geq 2$)and no vertices has degree of $2$, then $T$ has at least $\frac{n+2}{2}$ leaves. Prove by contradiction Suppose that $T$ has less than ...
0
votes
0answers
14 views

Problem with Hall's marriage theorem

Let P1={A1,A2,...,A10} and P2={B1,B2,...,B10} be two distinct partitions of a set of 100 people into groups of 10. Let G be a bipartite graph with P1 and P3 as bipartitions. There is an edge between ...
1
vote
2answers
41 views

Number of graph vertices of odd degree is even

This elementary result is normally stated as a corollary to the Handshaking Lemma, which says nothing about it other than that it's true. I wonder if there is more depth to this fact, in particular if ...
0
votes
0answers
13 views

Coefficient of Multinomial kind of expression

How do I find the Multinomial coefficient of expression. For example $(x+y+z+w+6)^8$ let say I want the coefficient of xyzw. I know the answer in the simple case of $(x+3)^5$ , for $x^2$ it will ...
0
votes
1answer
6 views

Vertex ideal in graphs?

Vertex ideal originates from lattices here. Is there some relationship to relate it to graphs such as series-parallel graphs?
1
vote
1answer
22 views

Connectivity vs clique number of a graph

Is there some known relationship between the connectivity $\kappa(G)$ and the clique number $\omega(G)$ of a graph? Just out of curiosity. In particular, is $\omega(G)$ bounded by some function of ...
0
votes
0answers
20 views

Graph Theory: Graph on torus

Show that one can draw $K_{5}$ , $K_{6}$ , $K_{7}$ on a torus. Torus: a square where opposite sides have been glued. No idea about how to proceed it :/
0
votes
0answers
12 views

what is reachable vertices meaning?

I did not get what is reachable vertex meaning,when i studied Minimum weight perfect matching. According to Hungarian method,the given matrix like below : \begin{matrix} 1 & 0 ...
0
votes
1answer
18 views

Proving spanning trees contain all pendant edges.

Illustrate and prove that each spanning that each spanning tree of a connected graph G contains all the pendant edges of G. I already know how to illustrate, however can't prove. It says I need to ...
2
votes
1answer
125 views

Get rid of `for` loops to construct $L$

I have a kind of implicit characterization of the adjacency matrix $L$ of a directed line graph of an undirected graph on $n$ vertices (each edge in the undirected graph is represented by a pair of ...
3
votes
1answer
77 views

What is an intuition behind permanent?

I would like to know what is your intuition behind permanent of a matrix. For me, it looks like someone came and saw determinant, deleted permutation sign and voila, we have permanent and it counts ...
0
votes
0answers
20 views

Every n circuits in R2 field

I've saw this question today, For every n circuits in R2 field that cut each other circle 2 times, the plane will divide into n(n-1)+2 areas. Iv'e tried to solve this by incution but I cant find the ...
0
votes
1answer
31 views

code or algorithm for the independent dominant number

dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in a ...
2
votes
1answer
22 views

Function as an eigenvector for a matrix?

So I am currently going through this paper: Link Here And in section 2.2, it defines $K$ to be a weighted adjacency matrix for a certain rectangular $n$ by $m$ graph, where the weights are all either ...
0
votes
0answers
18 views

How to prove the following facts regarding the matrix

Let $X$ be a connected graph on $n$ vertices and $n$ edges. Let $Q$ be its edge incidence matrix.If $T\subset \{1,2 ,n\}$ with $|T|=n-1$ then $\det (Q[1,2 ,n-1\mid T])=^+_- 1$ if and only if the ...
0
votes
0answers
18 views

3 regular graph, 10 vertices, non-adjacent vertices have common neighbour

How can I show the following: in any 3-regular graph with 10 vertices, every pair of non-adjacent vertices, has a common neighbour. I've seen on the internet that there are some very general proofs ...
0
votes
2answers
50 views

Adjacency Matrix of a Graph Length of Paths Proof

Let A be an adjacency matrix of a graph $G$. Prove that the $(i, j)^{th}$ entry of $A^2$ is the number of paths of length $2$ between vertex $i$ and vertex $j$. *I know the adjacency matrix will be a ...
0
votes
1answer
21 views

Claim: In every graph with at least 2 vertices you can always find 2 vertices with the same degree

This appeared as an excercise in my problem sheet at uni. How can this be true for any graph? Ive added a pic of a graph which fails. I've put the degree above the vertex. I did this on powerpoint- ...
0
votes
1answer
33 views

Is the Wikipedia article about chordal graphs incorrect?

This is the wiki for chordal graphs. It states that "A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and the neighbors of v that ...
0
votes
2answers
45 views

Nonexistence of digraph where all simple paths have the same cost

How to show that there is no strongly connected digraph $G=(V,E)$ where $E\neq\{\emptyset \}$, $|V|>2 $ with costs $c(e)\in \mathbb{R}$ for $e\in E$ such that every simple path $p$ in $G$ has the ...
0
votes
1answer
35 views

Graph with nine edges and all vertices of degree 3

There is a graph with nine edges and all vertices of degree 3? I don't think that this graph exist, but I don't know how to proof.
1
vote
2answers
1k 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 ...