Ear decompositions in combed graphs.
Edge Dominating Sets and Vertex Covers
Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.
Edge-disjoint 1-factors in powers of connected graphs
Edge-domatic number of a graph
Edge-domatic numbers of cacti
The edge-domatic number of a graph is the maximum number of classes of a partition of its edge set into dominating sets. This number is studied for cacti, i.e. graphs in which each edge belongs to at most one circuit.
Elementary proof of the reality of the zeros of beta-polynomials of complete graphs
Embedding graphs in their complements
Encodings of cladograms and labeled trees.
Enumeration of perfect matchings of a type of quadratic lattice on the torus.
Enumeration of tilings of diamonds and hexagons with defects.
Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)
Let be the family of all 2-connected plane triangulations with vertices of degree three or six. Grünbaum and Motzkin proved (in dual terms) that every graph P ∈ has a decomposition into factors P₀, P₁, P₂ (indexed by elements of the cyclic group Q = 0,1,2) such that every factor consists of two induced paths of the same length M(q), and K(q) - 1 induced cycles of the same length 2M(q). For q ∈ Q, we define an integer S⁺(q) such that the vector (K(q),M(q),S⁺(q)) determines the graph P (if P is...
Even [a,b]-factors in graphs
Let a and b be integers 4 ≤ a ≤ b. We give simple, sufficient conditions for graphs to contain an even [a,b]-factor. The conditions are on the order and on the minimum degree, or on the edge-connectivity of the graph.
Even factor of bridgeless graphs containing two specified edges
An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let be a bridgeless simple graph with minimum degree at least . Jackson and Yoshimoto (2007) showed that has an even factor containing two arbitrary prescribed edges. They also proved that has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges and of , there is an even factor containing and in which each...
Every graph is an induced isopart of a circulant
Existence of -factors in powers of connected graphs
Existence of perfect matchings in a plane bipartite graph
We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper of F. Zhang, R. Chen and X. Guo (1985).
Extremal bipartite graphs with a unique k-factor
Given integers p > k > 0, we consider the following problem of extremal graph theory: How many edges can a bipartite graph of order 2p have, if it contains a unique k-factor? We show that a labeling of the vertices in each part exists, such that at each vertex the indices of its neighbours in the factor are either all greater or all smaller than those of its neighbours in the graph without the factor. This enables us to prove that every bipartite graph with a unique k-factor and maximal size...
Extremal Matching Energy of Complements of Trees
Gutman and Wagner proposed the concept of the matching energy which is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph. And they pointed out that the chemical applications of matching energy go back to the 1970s. Let T be a tree with n vertices. In this paper, we characterize the trees whose complements have the maximal, second-maximal and minimal matching energy. Furthermore, we determine the trees with edge-independence number p whose complements have...
Extremal Unicyclic Graphs With Minimal Distance Spectral Radius
The distance spectral radius ρ(G) of a graph G is the largest eigenvalue of the distance matrix D(G). Let U (n,m) be the class of unicyclic graphs of order n with given matching number m (m ≠ 3). In this paper, we determine the extremal unicyclic graph which has minimal distance spectral radius in U (n,m) Cn.