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

2
votes
0answers
10 views

prove that the graph which is constructed with matrices is strongly regular

suppose that $F_q$ is a field with $q$ member,consider all $2\times d$ matrix with entries of $F_q$ ,so we have $q^{2d}$ matrix,consider each matrix as a vertex ,two vertex $A$ and $B$ are adjacent ...
0
votes
0answers
13 views

$G^k$ is k-connected - different approach for proof

Question: For a connected graph G = (V, E) and a positive integer k, let $G^k$ be the graph with vertex set V , where two vertices are connected by an edge if and only if their distance in G is at ...
2
votes
0answers
17 views

Structural / design / meta optimization - is there mathematical theory. Optimization over categories?

There is huge branch of mathematical optimization theory, but it mostly considers the finding optimal parameter values for the predefined structures. There are variational calculus and optimal control ...
3
votes
1answer
30 views

How many matroids with 1 element exist?

So we got the following question in the lecture: How many matroids with a single element exist? Couldn't really think of an answer. Any assistance would be of help!
4
votes
1answer
57 views

Composer's dilema - Graph Theory

I am a composer. I have 10, 30-second musical sections. The orchestra plays 5, five are played by a soloist. I would like to give them each choices. I have written the piece so that each section flows ...
6
votes
2answers
608 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
4
votes
1answer
261 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
0
votes
2answers
53 views

An identity that comes from computing the Wiener index of a cyclic graph [on hold]

Can the below identity be proven in such a way that we can generalize it? $(1 + 1 + 2 + 2 + 3 + 3 + 4) +( 1 + 2 + 2 + 3 + 3 + 4) + (1 + 2 + 3 + 3 + 4)+ +( 1 + 2 + 3 + 4 )+(1 + 2 + 3) + (1 + 2) + 1 = ...
5
votes
1answer
376 views

The number of paths on a graph of a fixed length w/o repeatings

Sorry for bad English. Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$. But what if we can't walk through a vertex ...
3
votes
1answer
46 views

$G^k$ is $k$-connected

For a connected graph $G$ on $n$ vertices and $1\le k \le n-1$ prove that the graph $G^k$ (where two vertices are connected if their distance is at most $k$) is $k$(-vertex)-connected. We need to ...
0
votes
2answers
63 views

The equality $\chi(G-v)=\chi(G)$

Let $G$ be a graph and $\deg(v)<\chi(G)-1$. By $\deg(v)$ and $\chi(G)$, I mean the degree of vertex $v$ and chromatic number of the graph $G$, respectively. I want to show that $\chi(G-v)=\chi(G)$. ...
3
votes
1answer
52 views

parity bias for trees?

Let $t(n)$ denote the number of unlabeled unrooted trees on n vertices, e.g. $t(4)=2$ . Next denote by $\operatorname{even}(n)$ the number of such trees having an even number of endpoints. Similarly, ...
2
votes
1answer
50 views

Mathematical name of this type of graph

If you have a tree that also might merge branches, but only in a directed way, i.e. all edges are one step either towards or away from the "root", what can we call it? It's a special case of a ...
-10
votes
0answers
53 views

Powers of $\frac12$ that sum to $1$ [on hold]

Call every subunitary ratio with its denominator a power of $2$ a perplex. Number $1$ can be written in many ways as a sum of perplexes. ...
2
votes
0answers
17 views

Spectral radius of a time-varying matrix with strictly positive increment

Consider a time varying non-negative matrix $A(t)$ and its spectral radius $\rho(A(t))$ where $t$ denotes the time. If $A(t)$ changes over time with each time a random element in $A(t)$ is being ...
3
votes
1answer
48 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...
0
votes
2answers
277 views

Cycle containing two given nodes in an undirected graph

Given an undirected graph G=(V,E) and two nodes s, t in V, how to FIND an arbitrary SIMPLE cycle (each node used only once) between s and t? Or just DETECT whether there is a cycle between them? Here ...
1
vote
1answer
55 views

Simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph

Why a simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph? In my notes, it says it is easy and leave as an exercise with a hint which want us to show the ...
0
votes
1answer
41 views

What is the probability of a chain of a given length in a random graph?

Let $G$ be an undirected graph with $n$ nodes. An edge is randomly and independently drawn from each node to any of the other nodes. If some arbitrary node $a$ is chosen, what is the probability that ...
1
vote
1answer
29 views

suppose $G$ is strongly regular graph srg$(n,k,\lambda,\mu)$,prove that $k\geq 2\lambda -\mu +3 $.

suppose $G$ is strongly regular graph srg$(n,k,\lambda,\mu)$,prove that $k\geq 2\lambda -\mu +3 $. I tried to show that $\mu(n-1)\geq k(\lambda+2)$(*) if I can prove that,then I add $-\mu k$ to both ...
0
votes
1answer
20 views

number of ways to label in a cycle

Suppose I have a 6 vertices complete graph, Say it G. It is labeled, Now I need to find all distinct 4 vertices cycles. So for first step there are 6C4 ways to select 4 length cycles , but as it is ...
0
votes
0answers
26 views

number of distinct simple graphs with n vertices?

To calculate simple, labelled graphs is easy with the formula $2^{n(n-1)/2}$, but if we say distinct, then it would certainly be less than it, because some possible situations will be same hence not ...
0
votes
1answer
35 views

Fundamental circuit and cut-set [on hold]

When Finding all the fundamental circuits and cut sets of $K_{3,3}$ and $K_5$ graph ,does planarity have any effect ?
1
vote
1answer
39 views

How to test that this 3D graph is rigid?

I have constructed a lattice as a 3D graph while ensuring that it is rigid. I would like to find a way to test it to verify. Any thoughts? Links to papers?
0
votes
1answer
22 views

How many $k$-regular bipartite graphs can I make given $n$ distinct vertices?

I'm attempting to solve a problem that I think can be solved best with graph theory. I know very little regarding graph theory, so excuse any misuse of vocabulary (which I only picked up in the last ...
3
votes
1answer
109 views

Prison break: a minimisation problem

Consider a prison with $n$ prisoners. Each cell contains a phone which can be used to call any other cell. Each prisoner has a different piece of information which, when put together, will ...
9
votes
1answer
303 views

Bipartite graph: how many closed walk with given properties

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices. We focus on closed walks of length $2L$. Such walks can be described by the sequence of ...
0
votes
0answers
26 views

Extension of a set of edges

Let $G$ be a graph and $F$ be a set of sedges of $G$. If $F$ has no odd cut, then $F$ can extend to an element of the cycle space of $G$. My attempt: I should add edges to $F$. I know that ...
1
vote
1answer
30 views

Maximum number of highways

There are 20 cities in a country, some of which have highways connecting them. Each highways goes from one city to another, both ways. There is no way to start in a city, drive along the highways of ...
2
votes
1answer
49 views

The circumference of a hypercube graph

How can I find the circumference of a hypercube graph? is easy to see that a n-dimensional hypercube have a $2n$-cycle, but I cant prove that it's the largest, can anybody help me?
2
votes
1answer
53 views

Is this random binary tree finite?

Consider the following procedure for generating a random binary tree: Starting with a full binary tree (i.e., each node has either two or no children) we iterate over the leaves and (independently) ...
1
vote
0answers
16 views

Expected Max Pseudotree Size

I'm working on a problem where I need to calculate the expected maximum pseudotree size in a randomly-generated pseudoforest with $n$ nodes. Expected maximum value is of course: $$ E(x) = ...
1
vote
2answers
45 views

Suppose $G$ and $G'$ are two graphs having $n$ vertices. For what values of $n$ is it possible for $G$ to have more components and edges than $G'$?

Suppose $G$ and $G'$ are two graphs having $n$ vertices.For what values of $n$ is it possible for $G$ to have more components and edges than $G'$? What could be the possible values of $n$?
5
votes
1answer
270 views

Disjoint paths on grid graphs

Let $f(G)$ be the smallest $m$, such that one can find $2m$ vertices in $G$ with the following property: pair up the vertices in any way, and find $m$ paths that join each pair. Then every set of path ...
2
votes
1answer
38 views

What is the smallest and the largest possible adjacency eigenvalue of a regular graph?

For a $d-$regular graph I think $d$ is always the largest adjacency eigenvalue and if its bipartite then I think $-d$ is the smallest possible.
0
votes
1answer
43 views

What is the solution to this graph question? [duplicate]

Hi everybody, is there anybody who can answer the following problem? I dont know how to start solving it, thank you very much.![the question is in the picture below][2]
0
votes
1answer
18 views

List (of) all cubic planar graph with 30 vertices

Where can I find the list of all possible cubic planar graphs (without triangles) having 30 vertices? Are there online databases for that?
1
vote
2answers
35 views

Tree with radius and diameter

How to show that a radius in a tree is not necessarily half its diameter ?? I'm using the following relation to prove but cannot find proper explanation 2*radius-1 ≤ diameter ≤ 2*radius Suggest if ...
0
votes
0answers
32 views

Checking if a relation is complete

I have a transitive relation $\subset$ on a (finite and small) set S and a list of pairs $x_i\subset y_i.$ I would like to check if my list is complete in the sense that if $x\subset y$ then there are ...
1
vote
1answer
17 views

What does this definition of an $H$-path mean?

I'm going through a graph theory book, which defines an $H$-path as follows: Given a graph $H$, we call $P$ an $H$-path if $P$ is non-trivial and meets $H$ exactly in its ends. In particular, the ...
5
votes
0answers
68 views

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all.

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all. I suppose there is no one who is friend to all,I want to show ...
0
votes
0answers
22 views

Finding all planar graphs with more regions than edges.

I want to find all planar graphs with more regions than edges. This is my solution. Let $G=(V,E)$ be a planar graph and pick a planar representation. If $G$ is connected, I can use Euler's formula. ...
2
votes
1answer
25 views

What is the relation between linear subgraph and matching polynomial?

I am confused about these following three concepts, An edge-cycle subgraph of a graph $G$ (also called a linear subgraph of $G$) is a subgraph of $G$ whose components are cycles and edges. A set of ...
1
vote
1answer
24 views

give an example to show it is possible to remove one vertex and the multiplicity of one of eigenvalue rise.

I know that if we consider a graph $G$ with $\lambda$ as one of its eigenvalue of adjacency matrix with multiplicity $n$ ,there is a vertex of $G$ that by removing it ,the multiplicity of $\lambda$ ...
6
votes
1answer
199 views

Powers of adjacency matrix doesn't seem to correspond to observed number of paths on graph

I would really appreciate some help on this! $A^n$ represents $n^{th}$ power of the adjacency matrix of a graph. I keep reading that the $A^n_{ij}$ entry equals "the number of paths of length n ...
0
votes
1answer
30 views

Is there any regular polyhedron that is not of Euler characteristic 2

Is there any regular polyhedron that 1. consist of congruent regular polygons as its faces 2. each vertex has same number of adjacent edges but nonetheless not of characteristic 2? (say, torus or ...
1
vote
3answers
32 views

Is there a 5-regular graph of order 7?

How can I decide if there is a 5-regular graph of order 7? Some hints or tips would be appreciated. This question arises in studying for a graph theory course.
0
votes
2answers
44 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
2
votes
1answer
550 views

If a graph with $n$ vertices and $n$ edges there must a cycle?

How to prove this question? If a graph with $n$ vertices and $n$ edges there must a cycle?
0
votes
1answer
65 views

Graph theory and tree company

I appreciate anyone who answer this question and I anyone who design appropriate graph.