| 1. |
- Asratian, Armen, 1951-
(författare)
-
New local conditions for a graph to be hamiltonian
- 2006
-
Ingår i: Graphs and Combinatorics. - : Springer Science and Business Media LLC. - 0911-0119 .- 1435-5914. ; 22:2, s. 153-160
-
Tidskriftsartikel (refereegranskat)abstract
- For a vertex w of a graph G the ball of radius 2 centered at w is the subgraph of G induced by the set M 2(w) of all vertices whose distance from w does not exceed 2. We prove the following theorem: Let G be a connected graph where every ball of radius 2 is 2-connected and d(u)+d(v)|M 2(w)|-1 for every induced path uwv. Then either G is hamiltonian or [InlineMediaObject not available: see fulltext.] for some p2 where denotes join. As a corollary we obtain the following local analogue of a theorem of Nash-Williams: A connected r-regular graph G is hamiltonian if every ball of radius 2 is 2-connected and [InlineMediaObject not available: see fulltext.] for each vertex w of G. © Springer-Verlag 2006.
|
|
| 2. |
- Asratian, Armen, et al.
(författare)
-
On Path Factors of (3,4)-Biregular Bigraphs
- 2008
-
Ingår i: Graphs and Combinatorics. - : Springer Science and Business Media LLC. - 0911-0119 .- 1435-5914. ; 24:5, s. 405-411
-
Tidskriftsartikel (refereegranskat)abstract
- A (3, 4)-biregular bigraph G is a bipartite graph where all vertices in one part have degree 3 and all vertices in the other part have degree 4. A path factor of G is a spanning subgraph whose components are nontrivial paths. We prove that a simple (3,4)-biregular bigraph always has a path factor such that the endpoints of each path have degree three. Moreover we suggest a polynomial algorithm for the construction of such a path factor.
|
|
| 3. |
- Asratian, Armen S., et al.
(författare)
-
Some panconnected and pancyclic properties of graphs with a local ore-type condition
- 1996
-
Ingår i: Graphs and Combinatorics. - 0911-0119 .- 1435-5914. ; 12:3, s. 209-219
-
Tidskriftsartikel (refereegranskat)abstract
- Asratian and Khachatrian proved that a connected graphG of order at least 3 is hamiltonian ifd(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| for any pathuwv withuv ∉ E(G), whereN(x) is the neighborhood of a vertexx.We prove that a graphG with this condition, which is not complete bipartite, has the following properties:a) For each pair of verticesx, y with distanced(x, y) ≥ 3 and for each integern, d(x, y) ≤ n ≤ |V(G)| − 1, there is anx − y path of lengthn. (b)For each edgee which does not lie on a triangle and for eachn, 4 ≤ n ≤ |V(G)|, there is a cycle of lengthn containinge. (c)Each vertex ofG lies on a cycle of every length from 4 to |V(G)|. This implies thatG is vertex pancyclic if and only if each vertex ofG lies on a triangle.
|
|
| 4. |
- Casselgren, Carl Johan, et al.
(författare)
-
Avoiding and Extending Partial Edge Colorings of Hypercubes
- 2022
-
Ingår i: Graphs and Combinatorics. - : Springer. - 0911-0119 .- 1435-5914. ; 38:3
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring φ of the d-dimensional hypercube Qd, we are interested in whether there is a proper d-edge coloring of Qd that agrees with the coloring φ on every edge that is colored under φ; or, similarly, if there is a proper d-edge coloring that disagrees with φ on every edge that is colored under φ. In particular, we prove that for any d≥ 1 , if φ is a partial d-edge coloring of Qd, then φ is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or φ is proper and every color appears on at most d- 2 edges. We also show that φ is avoidable if d is divisible by 3 and every color class of φ is an induced matching. Moreover, for all 1 ≤ k≤ d, we characterize for which configurations consisting of a partial coloring φ of d- k edges and a partial coloring ψ of k edges, there is an extension of φ that avoids ψ.
|
|
| 5. |
- Casselgren, Carl Johan, et al.
(författare)
-
Coloring Complete and Complete Bipartite Graphs from Random Lists
- 2016
-
Ingår i: Graphs and Combinatorics. - : Springer Science and Business Media LLC. - 0911-0119 .- 1435-5914. ; 32:2, s. 533-542
-
Tidskriftsartikel (refereegranskat)abstract
- Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.
|
|
| 6. |
- Chen, Guantao, et al.
(författare)
-
Extremal Union-Closed Set Families
- 2019
-
Ingår i: Graphs and Combinatorics. - : Springer Japan. - 0911-0119 .- 1435-5914. ; 35:6, s. 1495-1502
-
Tidskriftsartikel (refereegranskat)abstract
- A family of finite sets is called union-closed if it contains the union of any two sets in it. The Union-Closed Sets Conjecture of Frankl from 1979 states that each union-closed family contains an element that belongs to at least half of the members of the family. In this paper, we study structural properties of union-closed families. It is known that under the inclusion relation, every union-closed family forms a lattice. We call two union-closed families isomorphic if their corresponding lattices are isomorphic. Let F be a union-closed family and boolean OR(F is an element of F) F be the universe of F. Among all union-closed families isomorphic to F, we develop an algorithm to find one with a maximum universe, and an algorithm to find one with a minimum universe. We also study properties of these two extremal union-closed families in connection with the Union-Closed Set Conjecture. More specifically, a lower bound of sizes of sets of a minimum counterexample to the dual version of the Union-Closed Sets Conjecture is obtained.
|
|
| 7. |
- Cherkashin, Danila, et al.
(författare)
-
Erdős–hajnal problem for h-free hypergraphs
- 2024
-
Ingår i: Graphs and Combinatorics. - : Springer. - 0911-0119 .- 1435-5914. ; 40:1
-
Tidskriftsartikel (refereegranskat)abstract
- This paper deals with the minimum number mH(r) of edges in an H-free hypergraph with the chromatic number more than r. We show how bounds on Ramsey and Turán numbers imply bounds on mH(r) .
|
|
| 8. |
|
|
| 9. |
- Fröberg, Ralf, 1943-
(författare)
-
The Hilbert series of the clique complex
- 2005
-
Ingår i: Graphs and Combinatorics. - : Springer Science and Business Media LLC. - 0911-0119 .- 1435-5914. ; 21:4, s. 401-405
-
Tidskriftsartikel (refereegranskat)abstract
- For a graph G, we show a theorem that establishes a correspondence between the fine Hilbert series of the Stanley-Reisner ring of the clique complex for the complementary graph of G and the fine subgraph polynomial of G. We obtain from this theorem some corollaries regarding the independent set complex and the matching complex.
|
|
| 10. |
- Hellmuth, Marc, 1980-, et al.
(författare)
-
Injective Split Systems
- 2023
-
Ingår i: Graphs and Combinatorics. - 0911-0119 .- 1435-5914. ; 39:4
-
Tidskriftsartikel (refereegranskat)abstract
- A split system S on a finite set X, |X|≥3, is a set of bipartitions or splits of X which contains all splits of the form {x,X−{x}}, x∈X. To any such split system S we can associate the Buneman graph B(S) which is essentially a median graph with leaf-set X that displays the splits in S. In this paper, we consider properties of injective split systems, that is, split systems S with the property that medB(S)(Y)≠medB(S)(Y′) for any 3-subsets Y,Y′ in X, where medB(S)(Y)med denotes the median in B(S) of the three elements in Y considered as leaves in B(S). In particular, we show that for any set X there always exists an injective split system on X, and we also give a characterization for when a split system is injective. We also consider how complex the Buneman graph B(S) needs to become in order for a split system S on X to be injective. We do this by introducing a quantity for |X| which we call the injective dimension for |X|, as well as two related quantities, called the injective 2-split and the rooted-injective dimension. We derive some upper and lower bounds for all three of these dimensions and also prove that some of these bounds are tight. An underlying motivation for studying injective split systems is that they can be used to obtain a natural generalization of symbolic tree maps. An important consequence of our results is that any three-way symbolic map on X can be represented using Buneman graphs.
|
|
