Questions tagged [subgraph]
The subgraph tag has no usage guidance.
16 questions
0
votes
0
answers
46
views
Maximum subgraph of a strongly regular graph satisfying cohomology constraints
Consider the following strongly regular graph $G=(V,E)$ (constructed as the symplectic graph over $\mathbb F_2^{2r}$) with $r>1$ with parameters
$$
(n,k,a,c)=\left( 2^{2r}-1,2^{2r-1},2^{2r-2},2^{2r-...
- 111
3
votes
1
answer
241
views
Some questions about induced subgraphs of the directed hypercube graph
Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
- 129
1
vote
0
answers
140
views
Number of eulerian subgraphs of complete graph [closed]
I need an advice on how to approach this problem. It's a part of a project in Graph theory. How to determine a number of eulerian subgraphs of $K_n$ (complete graph with $n$ vertices)? It's part of a ...
- 31
5
votes
3
answers
411
views
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
- 1,444
1
vote
1
answer
68
views
Counting number of special subset of vertices in a tree
As defined in this article, an ordered pair $ (X,Y) $ of disjoint subsets of the vertices of a graph $ G $ with $ \vert X \vert = \vert Y \vert =2 $, is called an odd pair if the number of edges with ...
- 351
1
vote
0
answers
38
views
maximal k-partite subgraph in a complete multipartite graph
What is the maximum number of edges a $k$-partite subgraph of a complete $s$-partite graph can have?
Bests,
Josefran
- 11
2
votes
1
answer
170
views
About a generalization of complete graphs
Does anyone know what are called (if there is any nomenclature for this class of graphs in the literature) the connected graphs such that each of their edge belongs to some triangle? For example, ...
- 353
1
vote
1
answer
77
views
Number of occurrences of subgraphs as a unique identifier
Given $q \in \mathbb{N}$, let $B_q$ be a sequence of all (non isomorphic) connected graphs with at most $q$ vertices. Now for a given connected graph $G$, lets define signature of $G$ ($sig_q(G)$) as ...
- 11
1
vote
1
answer
448
views
Quotient graph of a tree
We know that every graph is isomorphic to a subgraph of a complete graph. Similarly, can we say that every graph is isomorphic to a quotient graph of a tree?
- 353
1
vote
0
answers
145
views
Symmetric subgraph configurations
Let $G,H$ be two simple graphs. Let's call a subgraph of $H$ that is isomorphic to $G$ a $G$-subgraph. Consider the following construction:
Construction: Let $\mathcal G=\mathcal G(G,H)$ be a graph ...
- 13.6k
0
votes
0
answers
80
views
When are the cardinalities of 2-factors in a graph equal?
Given a graph $G$, if we can partition the edges into pairwise disjoint subsets of $G$, such that the union of all the subsets is equal to the edgeset of G, then this is a decomposition. If such a ...
1
vote
2
answers
256
views
Maximum subgraph edge distance greater than given number
I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...
- 283
8
votes
1
answer
2k
views
A matching that covers vertices with maximum degree
We have a graph G with maximum degree $\Delta$. The induced subgraph on vertices with degree equal to $\Delta$ is a bipartite graph (while the original graph is not).
Prove that G has a matching that ...
- 400
1
vote
1
answer
192
views
Subgraph isomorphism problem on 2d triangular lattices.
Is there an efficient (possibly probabilistic/approximate) algorithm for determining whether a particular graph is the subgraph of an infinite two dimensional triangular lattice? How about three ...
1
vote
1
answer
1k
views
Minimum spanning subgraph with at least one incoming and one outgoing edge
Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which ...
- 723
1
vote
1
answer
390
views
almost-bipartite nearly-isolated subgraphs
I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is bipartite-plus-a-few-edges ...
- 6,962