Temat: complete bipartite graph

Skocz do pozycji: 1.

Tytuł:: Decompositions of Complete Bipartite Graphs and Complete Graphs Into Paths, Stars, and Cycles with Four Edges Each
Autorzy:: Shyu, Tay-Woei
Tematy:: complete graph
complete bipartite graph
path
star
cycle
decomposition; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32083883.pdf Link otwiera się w nowym oknie
Opis:: Let G be either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r > 0, for which there exists a decomposition of G into p paths, q stars, and r cycles, each of which has 4 edges.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Gallai-Ramsey numbers for rainbow trees and monochromatic complete bipartite graphs
Autorzy:: Li, Luyi
Li, Xueliang
Mao, Yaping
Si, Yuan
Tematy:: Ramsey theory
Gallai-Ramsey number
complete bipartite graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/63381384.pdf Link otwiera się w nowym oknie
Opis:: Given two non-empty graphs $G,H$ and a positive integer $k$, the Gallai-Ramsey number $\text{gr}_k(G:H)$ is defined as the minimum positive integer $N$ such that for all $n\geq N$, every $k$-edge-colored $K_n$ contains either a rainbow subgraph $G$ or a monochromatic subgraph $H$. In this paper, we get some exact values or bounds of $\text{gr}_k(K_{1,3}:H)$, $\text{gr}_k(P_5:H)$, and $\text{gr}_k(P_4^{+}:H)$ for $k\geq 3$, where $H$ is a complete bipartite graph.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: On 2-periodic graphs of a certain graph operator
Autorzy:: Havel, Ivan
Zelinka, Bohdan
Tematy:: graph operator
power and complement of a graph
Desarguesian finite projective geometry
decomposition of a complete bipartite graph
generalized hypercube; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743413.pdf Link otwiera się w nowym oknie
Opis:: We deal with the graph operator $\overline{Pow₂}$ defined to be the complement of the square of a graph: $\overline{Pow₂}(G) = \overline{Pow₂(G)}$. Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph $K_{m,n}$ can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective geometries belong to and find infinitely many graphs also belonging to among generalized hypercubes.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: The Complexity of Secure Domination Problem in Graphs
Autorzy:: Wang, Haichao
Zhao, Yancai
Deng, Yunping
Tematy:: secure domination
star convex bipartite graph
doubly chordal graph
NP-complete
APX-complete; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31342335.pdf Link otwiera się w nowym oknie
Opis:: A dominating set of a graph G is a subset D ⊆ V (G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u ∈ V (G) \ S has one neighbor v in S such that (S \ {v}) ∪ {u} is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1−ε) ln |V | for any ε > 0, unless NP⊆DTIME (|V |^{O(log log |V|})). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: Optimal edge ranking of complete bipartite graphs in polynomial time
Autorzy:: Hung, Ruo-Wei
Tematy:: graph algorithms
edge ranking
vertex ranking
edge-separator tree
complete bipartite graphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743901.pdf Link otwiera się w nowym oknie
Opis:: An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees and complete graphs, little has been known about special classes of graphs for which the problem can be solved in polynomial time. In this paper, we present a polynomial-time algorithm to find an optimal edge ranking for a complete bipartite graph by using the dynamic programming strategy.
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja