Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

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.

0
votes
0answers
7 views

Self-study Graph theory

I decided to self-study graph theory. I am not newbie in it as I have experience from programming, like I know graph algorithms and how they work, have some experience with discrete mathematics(well, ...
2
votes
0answers
16 views

The chromatic number of a graph is at most its circumference

The chromatic number of a graph is at most its circumference: the length of the longest cycle in the graph. (Making an exception for forests, where the chromatic number is at most $2$ and the ...
0
votes
2answers
13 views

Prove that a directed graph with no cycles has at least one node of indegree zero

How would I show this? I know a directed graph with no cycles has at least one node of outdegree zero (because a graph where every node has outdegree one contains a cycle), but do not know where to go ...
1
vote
2answers
31 views

Knowing every odd circuit in a graph is a triangle, prove $\chi(G) \le 4$ [duplicate]

Knowing every odd circuit in a graph is a triangle, prove $\chi(G) \le 4$ My approach: an odd circuit requires 3 colors, and an even circuit requires 2. But then I'm stuck. Can you give me a hint on ...
0
votes
0answers
11 views

Build a graph with uniform distribution [on hold]

I have 1000 points with (x,y,z) coordinates. From each node, beginning from (0,0,0) coordinates, 4 branches may be progressed to other nodes. The length of each branch should be less than ...
0
votes
1answer
20 views

Confusion about the definition of a graph property and it's relation to $G(n,p)$

We defined a graph property the following way: Let $\Omega_n$ be the set of all graphs $G = ([n], E)$ on $n$ nodes. Then, a graph property is a sequence $P = (P_n)_{n \in \mathbb N}$ with $P_n \...
2
votes
0answers
22 views

Spectral measure of a finite graph

Let $A$ be the adjacency operator of connected, locally finite graph $G = (V,E)$ ($A$ seen as an operator on $\ell^2(V)$). Then we have the spectral representation $$ A = \int_{\sigma(A)} t \mu(dt)$$ ...
1
vote
0answers
17 views

Minimal one-step distance set of vertices to all vertices

I want to find minimal set of vertices such that every vertex in this graph either in this set or connected with some vertex from this set with one edge. Is there standard name for this algorithm? It ...
0
votes
1answer
21 views

edge deletions and spanning subgraphs

The following is from Graphs and Digraphs 6th Edition by Chartrand, Lesniak and Zhang: For a vertex $v$ and an edge $e$ in a nonempty graph $G = (V, E)$, the subgraph $G-v$, obtained by deleting $...
1
vote
1answer
16 views

Chromatic index of planar 4-regular graphs

Planar graphs of max degree 4 are, in general, not necessarily edge-4-colorable. However, what is the situation if the graph is 4-regular, is it edge-4-colorable? I am guessing this is known ... ...
3
votes
1answer
55 views

Can you prove $K_{3,3}$ is not planar without the Jordan Curve Theorem?

The non-planarity of $K_{3,3}$ is well know and e.g. shown here: 3 Utilities | 3 Houses puzzle? However, it is pointed out that the given proofs all use the Jordan Curve Theorem in one form or ...
1
vote
1answer
25 views

$G$ is a forest if and only if every connected subgraph is induced

G is a forest -> every connected subgraph of G is induced Definition of a induced subgraph: for x,y in V(F), xy is in E(F) if and only if xy is in E(G) Proof: Be F a connected subgraph of G. Suppose ...
1
vote
0answers
12 views

Name for a digraph having at most one path between any 2 nodes?

I have used the notion of a directed graph which has at most one path between any two nodes (examples: trees, complete bipartite graph) in a research paper on a topic only tangentially related to ...
1
vote
0answers
16 views

Number of permutation matrices within a distance of a given matrix

Given a matrix $M$, and a permutation $P_0$, is it possible to easily count, or easily approximately count, the number of permutation matrices $P$ that satisfy $\|P - M\| = \|P_0 - M\|$? What about ...
0
votes
0answers
16 views

Compute the shortest path in a directed acyclic graph

Problem: Let $D = (V,A)$ be a directed acyclic graph, i.e., there exists no directed cycle in D, and let $w : A → R$ be arc weights. Assume that you are given a topological sort of the vertices. Show ...
0
votes
0answers
20 views

Bichromatic graph

There is a complete bichromatic graph with shares of 300 and 500 vertices. What is the minimum number of colors in which edges and vertices can be painted in such a way that there are no: 1) ...
0
votes
0answers
26 views

Expectation of number of hubs in a random graph

Suppose $\Gamma(V, E)$ is a finite simple graph. Let’s call a vertex $v \in V$ a hub if $deg(v)^2 > \Sigma_{w \in O(v)} deg(w)$. Here $deg$ stands for the vertex degree, and $O(v)$ for the set of ...
0
votes
2answers
22 views

Find number of leaves of a tree (Proof)

Problem: Let $T$ be a tree that has $i\ge1$ branch nodes, all of which have the same degree[1] $d$. Show that the number of leaves $(l)$ of the tree can be calculated via the following formula: $$l=(...
2
votes
0answers
41 views

The spectral radius of Markov's averaging operator for the lattice graph $\mathbb{Z}^n$ is $1$

The spectral radius of Markov operator for the lattice graph $\mathbb{Z}^n$ is $1$ The lattice graph $\mathbb{Z}^n$ is defined as $V=\mathbb{Z}^n , E=\{ \{\vec{x} , \vec{y}\} : \vec{x},\vec{y}\in \...
0
votes
0answers
20 views

Elimination tree of a Cholesky factorization

I am failing to understand what the elimination tree of a Cholesky factorization is. For example given the matrix(source: https://aaronschlegel.me/cholesky-decomposition-r-example.html): $$A = \begin{...
0
votes
0answers
13 views

Finding a Hamiltonian Cycle from a perfect matching on a the bipartite graph

A disjoint vertex cycle cover can be found by a perfect matching on the bipartite graph constructed from the original graph (L) and its copy (R) and with L original graph edges replaced by ...
3
votes
2answers
40 views

Coloring Complete Graph

Let $n$ be a positive odd integer. There are $n$ computers and exactly one cable joining each pair of computers. You are to colour the computers and cables such that no two computers have the same ...
1
vote
1answer
23 views

Self-complementary graph with 4k+1 vertices, which is 2k-regular [duplicate]

Prove that ∀k∈N, k≥1, there is a self-complementary graph with 4k+1 vertices, which is 2k-regular. I think that the best way to prove it is by induction. Any helpful suggestions? (I know that this ...
1
vote
1answer
31 views

Question about self-complementary graphs

Question Prove that for every integer k≥1, exists a self-complementary graph with 4k vertices half of which are of degree 2k-1 and the other half of degree 2k. My approach So, I think the easiest way ...
1
vote
1answer
45 views

Proof that chromatic number is $< 9$

Let $G= (V,E)$ be a graph such that: $E = E_1 \cup E_2$ $G_1 = (V, E_1)$ is planar $G_2 = (V, E_2)$ is forest Proof that chromatic number is $< 9$ My observations Each planar graph has ...
0
votes
0answers
19 views

Tounament has champion [duplicate]

Let $G(V,E)$ be a simple directed graph such that • for each pair of vertices $u\neq v$, exactly one of the two edges $(u,v)$ or $(v,u)$ is in $E$ Prove that there is a vertex $s \in V$ such that ...
0
votes
1answer
33 views

eigenvalue of a graph

What does the eigenvalue of a graph mean? I know how to compute the eigenvalues from the adjacency matrix representation of a graph but am interested in its physical significance. If two graphs have ...
0
votes
0answers
44 views

Minimum number of lines that can cover all points in a graph

Say there are $n$ vertices in a graph. What is the minimum number of paths required to pass through all the $n$ vertices, given that the corner-most vertex is the endpoint of all the paths? There is a ...
2
votes
0answers
47 views

Proof of familiarity between 9 people

How can we try to prove that among any 9 people thare are 3 people who are familiar with each other or 4 who are not familiar with each other? My approach: I try to convert this to graph theory. So ...
0
votes
0answers
18 views

Number of walks in a looped Vertex (path)

If there is a vertex, V1. And V1 has a loop around itself. Why are there 4 walks around the loop? Apologies, an error comes up when i attach an image, so I've got to describe the image with words. ...
0
votes
0answers
18 views

Rosa's theorem about tree T with m edges to decompose a complete with 2m+1 vertice

In this theorem Rosa tell us that if there exist a tree T is graceful with m edges, then K_2m+1 could be decomposed into 2m+1 copies of tree T. But I want to ask that should the 2m+1 copies be ...
1
vote
0answers
16 views

How to construct conceptual models for graphs?

Construct conceptual models for the following types of graphs, using either ORM (Object-Role Modeling), ER (Entity-Relationship), or UML Class Diagrams: Directed graphs consist of nodes and directed ...
0
votes
0answers
24 views

Formulate a labeled directed graph

Given a labeled directed graph $〈N,E,l〉$ with $N$ a set of vertices, $E \subseteq N\times N$ a set $L$ to edges. Let source and target be functions on $E$ such that source$(s,t)=s$ and target $(s,t)=t$...
1
vote
1answer
17 views

How do you find all minimal vertex cover of bipartite graph $G$?

Let $G$ be a bipartite graph with vertex set $V=V_1 \cup V_2$. If $\mid V_1\mid= n$ and $\mid V_2\mid=m$ with $m\leq n$, then how to find all minimal vertex cover?
0
votes
0answers
47 views

prove that if $G$ is a graph with $n$ vertices and $\delta(G) \geq (n - 1) / 2$ then $G$ is $\frac{n-1}{2}$-edge-connected

So I know $G$ is connected since $\delta(G)\geq(n-1)/2$, we can simply prove it by contradiction. My approach to this question is use contradiction. Suppose that $G$ is not $\frac{n - 1}{2}$- edge - ...
0
votes
2answers
23 views

Prove that the degree of 2 vertices, which are the start and end of the longest path in a graph, are less than or equal to the length of the path

Let $G$ be a graph, and $P$ be the longest path in $G$. Let $x$ and $y$ be the start and end vertices of $P$ and let $m$ be the length of $P$. Prove that $deg(x)\le m$ and $deg(y)\le m$ for any graph $...
1
vote
0answers
18 views

Counting hypermaps with following properties

A $\textit{hypermap}$ of type $(g,n)$ is a graph embedded in an oriented surface of genus $g$ such that 1) the complement of the graph is the disjoint union of $n$ topological disks labelled from 1 ...
1
vote
1answer
21 views

Cospectral graphs that are non-isomorphic and that only have simple eigenvalues

It is a well known fact that there are non-isomorphic connected graphs whose adjacency matrix have the same spectrum. This has been discussed, for example, in this older post. However, in the ...
0
votes
0answers
13 views

(generalization) Maximum number of edges without a cycle of length k

I am baffled by the following solution to the problem from the Proofs from the Book. I was struggling with understanding the condition of not having a 4-cycle (C4) inside the graph. It seems to me to ...
1
vote
0answers
24 views

Doubt in vertex connectivity less than edge connectivity proof

Sir i recently started graph theory. Pls clarify my doubt. I understood the reason why edge connectivity is less than min degree(remove all vertices incident to min degree vertex). I have doubt in ...
0
votes
0answers
23 views

Prove that if a graph is k-connected, then it is also k-edge-connected

Here is my thought, first if it is k-connected, then every vertex has degree at least k. So removing a set of size k-1 edges will not result any isolated vertices. I don't know how to continue.
0
votes
0answers
37 views

Maximum number of distinct triangles in complete graph such that each edge appears in exactly two triangles

What's the maximum number of distinct triangles in complete graph of n vertices such that each edge of the graph appears in exactly two triangles? Maybe with the way to construct them? I hope I ...
0
votes
0answers
10 views

Node->cycle to lower Crossing Number

Here's a $K_{10}$ complete graph with each node replaced by a $C_{9}$ 9-cycle. ...
0
votes
0answers
8 views

A finite graph is always $r(B)$-recurrent

Let $G = (V, E)$ be a connected, locally finite graph. Let $B = B(G)$ be an arbitrary matrix associated with $G$ having the property $$\begin{cases} b_{u,v} > 0 & \text{if } [u,v] \in E,\\ b_{u,...
2
votes
2answers
50 views

Prove self-complementarity of regular graph with given order.

I am really stuck with the following graph problem: Prove that for any natural $k\ge1$, there is a self-complementary graph of order $4k+1$ such that it is $2k$-regular. I have a hint to use ...
0
votes
0answers
16 views

Find the minimum positive integer $r$ for which there exists an $r$-regular graph $G$ such that $\kappa(G) \neq \lambda(G)$

Find the minimum positive integer $r$ for which there exists an $r$-regular graph $G$ such that $\kappa(G) \neq \lambda(G)$. Verify your answer. (Chartrand, Gary, and Ping Zhang. A First Course in ...
3
votes
1answer
79 views

Coloring of rectangle $3\times 4$

We are colorings fields of rectangle with $3$ rows and $4$ columns in use of $2$ colors. Two colorings are the same if one is created from second in use any permutation of rows and cyclic shift of ...
0
votes
0answers
10 views

Is any orientation of a vertex-transitive and edge-transitive graph also arc transitive?

I have the following argument, I think it's wrong but I dont know how. Let $\overrightarrow{G}$ be an orientation of $G$, and let $\Phi : E(G) \rightarrow A(\overrightarrow{G})$ be a bijective ...
1
vote
1answer
33 views

1-factor in r-connected graph

I have this problem in graph theory: Let G be an r-connected graph of even order having no $K_(1,r+1)$ as an induced subgraph, for some r ≥ 1. Prove that G has a 1-factor. So there are two ...
4
votes
0answers
45 views

how are characterized categories that are determined by they graph up to isomorphism?

I know that thin categories have this property, but i also know that they are not the only ones. What are other kinds of categories that have this property? Is there any characterization of that fact?(...