Matrix partitions with finitely many obstructions.
Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs
Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs
Maximal graphs with respect to hereditary properties
A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property ; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P...
Maximum degree growth of the iterated line graph.
Median and quasi-median direct products of graphs
Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of G×P₃ is median if and only if G is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form G×K₂ are proved, and it is shown that the only nonbipartite quasi-median direct product is K₃×K₃.
Median properties of graphs with small diameters
Two numerical invariants and of a graph, related to the concept of median, are studied.
Minimal claw-free graphs
A graph is a minimal claw-free graph (m.c.f. graph) if it contains no (claw) as an induced subgraph and if, for each edge of , contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.
Minimal cycle bases of the lexicographic product of graphs
A construction of minimum cycle bases of the lexicographic product of graphs is presented. Moreover, the length of a longest cycle of a minimal cycle basis is determined.
Minimal trees and monophonic convexity
Let V be a finite set and 𝓜 a collection of subsets of V. Then 𝓜 is an alignment of V if and only if 𝓜 is closed under taking intersections and contains both V and the empty set. If 𝓜 is an alignment of V, then the elements of 𝓜 are called convex sets and the pair (V,𝓜 ) is called an alignment or a convexity. If S ⊆ V, then the convex hull of S is the smallest convex set that contains S. Suppose X ∈ ℳ. Then x ∈ X is an extreme point for X if X∖{x} ∈ ℳ. A convex geometry on a finite set is...
Modular and median signpost systems and their underlying graphs
The concept of a signpost system on a set is introduced. It is a ternary relation on the set satisfying three fairly natural axioms. Its underlying graph is introduced. When the underlying graph is disconnected some unexpected things may happen. The main focus are signpost systems satisfying some extra axioms. Their underlying graphs have lots of structure: the components are modular graphs or median graphs. Yet another axiom guarantees that the underlying graph is also connected. The main results...
More forbidden minors for wye-delta-wye reducibility.
More on even [a,b]-factors in graphs
In this note we give a characterization of the complete bipartite graphs which have an even (odd) [a,b]-factor. For general graphs we prove that an a-edge connected graph G with n vertices and with δ(G) ≥ max{a+1,an/(a+b) + a - 2} has an even [a,b]-factor, where a and b are even and 2 ≤ a ≤ b. With regard to the edge-connectivity this result is slightly better than one of the similar results obtained by Kouider and Vestergaard in 2004 and unlike their results, this result has no restriction on the...