Domatically cocritical graphs
A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
Let G₁ and G₂ be disjoint copies of a graph G, and let f:V(G₁) → V(G₂) be a function. Then a functigraph C(G,f) = (V,E) has the vertex set V = V(G₁) ∪ V(G₂) and the edge set E = E(G₁) ∪ E(G₂) ∪ {uv | u ∈ V(G₁), v ∈ V(G₂),v = f(u)}. A functigraph is a generalization of a permutation graph (also known as a generalized prism) in the sense of Chartrand and Harary. In this paper, we study domination in functigraphs. Let γ(G) denote the domination number of G. It is readily seen that γ(G) ≤ γ(C(G,f))...
Generalized Petersen graphs are certain graphs consisting of one quadratic factor. For these graphs some numerical invariants concerning the domination are studied, namely the domatic number , the total domatic number and the -ply domatic number for and . Some exact values and some inequalities are stated.
A graph is edge cycle extendable if every cycle C that is formed from edges and one chord of a larger cycle C⁺ is also formed from edges and one chord of a cycle C' of length one greater than C with V(C') ⊆ V(C⁺). Edge cycle extendable graphs are characterized by every block being either chordal (every nontriangular cycle has a chord) or chordless (no nontriangular cycle has a chord); equivalently, every chord of a cycle of length five or more has a noncrossing chord.
For two positive integers r and s, 𝓖(n;r,s) denotes to the class of graphs on n vertices containing no r of s-edge disjoint cycles and f(n;r,s) = max{𝓔(G):G ∈ 𝓖(n;r,s)}. In this paper, for integers r ≥ 2 and k ≥ 1, we determine f(n;r,2k+1) and characterize the edge maximal members in 𝓖(n;r,2k+1).
For a simple graph, we consider the minimum number of edges which block all the odd cycles and the maximum number of odd cycles which are pairwise edge-disjoint. When these two coefficients are equal, interesting consequences appear. Similar problems (but interchanging “vertex-disjoint odd cycles” and “edge-disjoint odd cycles”) have been considered in a paper by Berge and Fouquet.
In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.
Disjoint paths have applications in establishing bottleneck-free communication between processors in a network. The problem of finding minimum delay disjoint paths in a network directly reduces to the problem of finding the minimal disjoint paths in the graph which models the network. Previous results for this problem on chordal graphs were an O(|V| |E|²) algorithm for 2 edge disjoint paths and an O(|V| |E|) algorithm for 2 vertex disjoint paths. In this paper, we give an O(|V| |E|) algorithm for...
We prove that a countable connected graph has an end-faithful spanning tree that contains a prescribed set of rays whenever this set is countable, and we show that this solution is, in a certain sense, the best possible. This improves a result of Hahn and Širáň Theorem 1.