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
0answers
17 views

Canonical forms for matrices with binary elements.

Based on this answer to a combinatorics question I grew curious of results regarding similarities or canonical forms of matrices fulfilling these criteria: Elements of matrix are binary valued ...
1
vote
0answers
11 views

Wouldn't the asymptotes of the 2D projection of the inverse of the Riemann Zeta function show the real part of all the non-trivial zeros?

Can somebody provide a visualization of $z=\frac{1}{\zeta(x+iy)}\pm N$ for some large $N$ projected onto the $xz$-plane? I would imagine that if we found any asymptotes converging anywhere other than ...
1
vote
0answers
29 views

Find subgraph with maximum number of edges

Suppose there is a simple graph G. Is there a way to find a subgraph with a maximum of edges, for a certain number of vertices m?
1
vote
0answers
36 views

Probability Assessment of Interactive Markov Chain (IMC)

Firstly, consider a Markov chain in your mind. Probability of each state of the Markov chain can be obtained by following Chapman–Kolmogorov equation. $$ P(n\Delta t) = M^{n}P(0) $$ where P is the ...
1
vote
0answers
121 views

$(r+1)$ Clique of Induced subgraph and Turan’s theorem

$G$ is a $s$ regular graph. $A$ is a set of vertices where $|A| = s$ and $A \subseteq G$. $E$ is the number of edges of $G$. $n$ is the total number of vertices of $G$. Problem: Find the lower ...
1
vote
0answers
42 views

Graphs with disjoint edge sets

Consider a fixed set of vertices $\{v_1,v_2,\ldots,v_m\}$ and a family of graphs $G_1, G_2, \ldots, G_n$ on these vertices such that no two graphs share an edge. In other words, if $E(G_i)$ is the ...
1
vote
0answers
21 views

Yet another curious convolution

Some time ago, I found the following algorithmic problema: Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors. Given that the ...
1
vote
0answers
36 views

Expected number of random sub-cliques neccessary to cover a complete graph

I have the following problem: Given a complete, simple graph, i.e., a graph $(V,E)$ where every possible edge is realized, so $|E| = \frac{|V||V-1|}2$. Now consider complete sub-graphs, or ...
1
vote
0answers
40 views

Is there a name for this particular kind of tree graph?

I've recently encountered a problem which heavily involves analysis of structures analogous to weighted trees with no nodes of degree two (such a node along with its adjacent edges would be ...
1
vote
0answers
86 views

The Earth-Moon Map Problem

The following is the Sulanke Earth-Moon Map. A planet and moon have each been divided into eleven contiguous regions. In both maps, the regions 1-3, 3-5, 5-2, 2-4, and 4-1 do not touch, while all ...
1
vote
0answers
30 views

Binary Minimum Spanning Tree (from complete graph)

Given a weighted complete graph (or more exactly, a matrix of pairwise metric distances between vertices), I need to find a good approximation of the binary spanning tree of lowest total cost. There ...
1
vote
0answers
32 views

On the LowerBound for the number of edges of a simple connected graph on $n$ vertices.

We know that if $G$ is a simple graph on $n$ vertices and if $G$ has $k$ components then the number of edges $m$ of $G$ has the lower bound: $n-k\leq m$. The proof of one of a reference book on ...
1
vote
0answers
31 views

What kind of topological sorting exists in graph theory and what are their graphic plotting?

I know that there is at least two kinds of topological sorting: "by rank" and by"level" a level of a vertex is the maximal length of a path with x as an extremity. a rank of a vertex is the maximal ...
1
vote
0answers
21 views

Name of operation: changing the root of a rooted tree

What is (if any) the name of the operation of changing the root of a rooted tree? Picking a vertex which is not the root, then reorienting the edges in such a way that the vertex becomes the root?
1
vote
0answers
37 views

Graph having bounded degree

A graph is said to have bounded degree if there exists $N \in \mathbb{N}$ such that, for every $x \in V$, one has $\sum\limits_{y \in V} A_{x,y} \le N$. Show that, in this case, for any $f \in ...
1
vote
0answers
51 views

Degree/diameter problem for the even girth case

Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define $$n_0(g,\delta) := \begin{cases} 1 + \delta + \delta(\delta-1) + \cdots + ...
1
vote
0answers
30 views

Proof of properties of paths with distinct parities

I'm trying to work on this theorem, but I can't reach anywhere. Let $P$ and $Q$ be paths in a graph $G$ such that the end of $P$ is the same as the beginning of $Q$. Let $u$ be the first vertex ...
1
vote
0answers
23 views

Covariance estimation and Graphical Modelling

I've started reading on Convariance Matrix estimation through Graphical model in high-dimensional situation. But I have several questions. Suppose, $X_i \overset{iid}{\sim} N_p(\mu,\Sigma)$, ...
1
vote
0answers
45 views

Maximum independent edge set in multipartite graphs

The Hopcroft-Karp algorithm finds a maximum matching of an undirected, unweighted bipartite graph $G=(E,V)$ in $\mathcal{O}(|E|\sqrt{|V|})$ operations. Is there a generalization fo $k$-partite graph?
1
vote
0answers
30 views

Vertify an equivalent condition for feasible circulation

A circulation in a directed graph $D$ is a function $g:E(D)\rightarrow\mathbb{R}$ satisfying the conservation condition at every vertex. Let $l,u:E(D)\rightarrow \mathbb{R}^{+}_{0}$ be a lower and ...
1
vote
0answers
40 views

Graph isomorphism in terms of permutation matrix elements

The graph isomorphism problem is defined as follows. If $\Gamma_1$ and $\Gamma_2$ are two graphs with adjacency matrices $A_1$ and $A_2$ respectively, is there a permutation $\pi$ such that ...
1
vote
0answers
100 views

Cut distance between two random graphs

I am studying the cut metric from Large Networks and Graph Limits by Lovasz and need help proving one of the statements. On page 128, it says that the cut distance between two independent random ...
1
vote
0answers
29 views

Good embeddings for degree-diameter graphs

I've put together a degree-diameter notebook for various graphs of the degree diameter problem. My favorite table is at The (Degree,Diameter) Problem for Graphs. Here are sample edge lists without ...
1
vote
0answers
12 views

Question regarding isomorphisms formed by deleting various edges in a plane triangulation…

Consider a plane triangulation $T$ with $m$ edges numbered $1, 2, … , m$. Form the near-triangulation $G_k$ by deleting the edge $e_k$ in $T$. Suppose the $m$ near-triangulations $G_k$ for $k = 1, 2, ...
1
vote
0answers
25 views

Obtain cycles with $a < $ nr. of edges $< b$

I have a chemistry/mathematical problem and I would like to get your opinion. Imagine you are generating a planar, cyclic molecule, with a total $N$ is the number of atoms. By Euler graph theory, the ...
1
vote
0answers
48 views

To find out the minimum required jumper number between objects

I try to find out the minimum required jumper number for connection between objects. The rule is : all objects are on a plane and need to connect all objects with only one connection. The minimum ...
1
vote
0answers
47 views

Independence of Events in Lovasz Local Lemma

Let $G$ be a (finite) graph with maximum degree $d$ and vertices $v_{1}, \dotsc ,v_{n}$. Let us associate an event $A_i$ with $v_i (i = 1, . . . , n)$ and suppose that $A_i$ is independent of the ...
1
vote
0answers
49 views

Conjecture on different type of triangle in a complete graph?

How many different triangles are there in $K_5$? The Answer is 35.(The Moscow Mathematics Puzzle) Then I asked what about $K_6$, $K_7$ and so on ...? With my intuition I arrived at this ...
1
vote
0answers
29 views

Understanding ILP formulations of combinatorial optimisation problems

I am having trouble understanding and producing integer linear programming formulations for combinatorial optimisation problems. I can understand basic ones like the knapsack problem: $min \quad ...
1
vote
0answers
47 views

A cubic simple graph without cut edges is matching covered

I recently found the following exercise: Given a cubic, simple undirected graph $G$ without cut edges, then $G$ is matching covered. I.e. every edge is contained in a perfect matching. My idea ...
1
vote
0answers
75 views

Eigenvectors of graph laplacian

Let $L$ be the laplacian matrix of a graph $G$, i.e. $L = D - A$, where $D$ is the degree matrix, and $A$ the adjacency matrix. Let $v_i$ be an eigenvector of $L$. Let $x,y$ be two vertices of the ...
1
vote
0answers
21 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
vote
0answers
98 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
26 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
34 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 ...
1
vote
0answers
62 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 ...
1
vote
0answers
74 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.
1
vote
0answers
14 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$ ...
1
vote
0answers
25 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
0answers
51 views

A question regarding matchings in bipartite graphs

Let $G=(V,E)$ be a graph with $V(G)=X\cup Y$, let $M_1$ be a matching that "covers" $X'\subseteq X$, and let $M_2$ be a matching that "covers" $Y'\subseteq Y$. Show that then there is a matching $M$ ...
1
vote
0answers
94 views

Optimal allocation in network

We want to analyse specialization matters in a given network (N,g). Nodes represent individuals that can produce goods and services (just like in our usual economy) and that can be consumers too. ...
1
vote
0answers
52 views

Graph Theory: Find optimal subgraph that contains a certain node and a fixed number of nodes

I have a connected graph $G$ and a real-valued function $f$ on sub-graphs $G' \subseteq G$. Given a node $n \in G$ and a positive integer $s$, I am looking for the connected subgraph $G' \subseteq G$ ...
1
vote
0answers
83 views

How coefficients from finite field can form ring of polynomials?

Let us consider a graph $G(V,E),$ where $V$ is the set of nodes and $E$ is the set of edges. $\mathbf{x}=[X_1,\ldots,X_r]$ are symbols multicast by source to $|T|$ sink nodes. Symbols are from ...
1
vote
0answers
62 views

what are these kind of graphs called in graph theory ?

Suppose the graph $G$ (here, we assume this graph is self-looped, i.e., each vertex is connected to itself) satisfies the following condition. For each vertex $v$ in $V(G)$, there is another vertex ...
1
vote
0answers
107 views

Directed Acyclic Graph - root and leaf node terminology

I have found conflicting terminology regarding how to label nodes in directed acyclic graphs. Specifically, I am looking for a definition of root and leaf nodes (preferably something to cite). For ...
1
vote
0answers
24 views

Multigraphic Degree Sequences

Given a degree sequence $\{d_1,d_2,\ldots,d_n\}$, can I determine in polynomial time in $n$ whether this sequence is multigraphic AND can be realized by a connected multigraph? Looking at this ...
1
vote
0answers
56 views

An extremal coloring problem

Is it true that there is $c\in\big[\frac{n}2,n+1\big]\cap\Bbb Z$ such that following holds if you assign single color to each edge of complete graph $K_n$: If $c$ colors are used in total, then ...
1
vote
0answers
90 views

Graph Theory number of handshakes of couples

This is an Olympiad question which I now know the answer to, but I am a bit unsatisfied with it. So maybe someone can shed some light: Question: $5$ couples go to a party. Each person shakes the ...
1
vote
0answers
64 views

Graph Theory:Folkman Graph

I want to prove that Folkman graph is edge transitive but not vertex transitive, and I don't know how can I start to prove, any help would be great thanks.
1
vote
0answers
17 views

Size of intersection of balls on non-ameanable graphs

Let $G$ be a vertex-transitive non-ameanable graph and let $B(x,n)$ be the ball of radius $n$ centered on the vertex $x$. I am interested in estimates on the cardinality of the following set, ...