Temat: complete bipartite graphs

Skocz do pozycji: 1.

Tytuł:: A Characterization for 2-Self-Centered Graphs
Autorzy:: Shekarriz, Mohammad Hadi
Mirzavaziri, Madjid
Mirzavaziri, Kamyar
Tematy:: self-centered graphs
specialized bi-independent covering (SBIC)
generalized complete bipartite graphs (GCB); Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31342444.pdf Link otwiera się w nowym oknie
Opis:: A graph is called 2-self-centered if its diameter and radius both equal to 2. In this paper, we begin characterizing these graphs by characterizing edge-maximal 2-self-centered graphs via their complements. Then we split characterizing edge-minimal 2-self-centered graphs into two cases. First, we characterize edge-minimal 2-self-centered graphs without triangles by introducing specialized bi-independent covering (SBIC) and a structure named generalized complete bipartite graph (GCBG). Then, we complete characterization by characterizing edge-minimal 2-self-centered graphs with some triangles. Hence, the main characterization is done since a graph is 2-self-centered if and only if it is a spanning subgraph of some edge-maximal 2-self-centered graphs and, at the same time, it is a spanning supergraph of some edge-minimal 2-self-centered graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

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ł

Skocz do pozycji: 3.

Tytuł:: Vertex-Distinguishing IE-Total Colorings of Complete Bipartite Graphs K_m,N(m < n)
Autorzy:: Chen, Xiang’en
Gao, Yuping
Yao, Bing
Tematy:: complete bipartite graphs
IE-total coloring
vertex-distinguishing IE-total coloring
vertex-distinguishing IE-total chromatic number; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30146641.pdf Link otwiera się w nowym oknie
Opis:: Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C(u) be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_ie^vt(G), and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. VDIET colorings of complete bipartite graphs K_m,n(m < n) are discussed in this paper. Particularly, the VDIET chromatic numbers of K_m,n(1 ≤ m ≤ 7, m < n) as well as complete graphs K_n are obtained.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: The $m$-bipartite Ramsey number $BR_m(H_1,H_2)$
Autorzy:: Rowshan, Yaser
Tematy:: Ramsey numbers
bipartite Ramsey numbers
complete graphs
$m$-bipartite Ramsey number; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59898658.pdf Link otwiera się w nowym oknie
Opis:: In a $(G^1,G^2)$ coloring of a graph $G$, every edge of $G$ is in $G^1$ or $G^2$. For two bipartite graphs $H_1$ and $H_2$, the bipartite Ramsey number $BR(H_1, H_2)$ is the least integer $b\geq 1$, such that for every $(G^1, G^2)$ coloring of the complete bipartite graph $K_{b,b}$, results in either $H_1\subseteq G^1$ or $H_2\subseteq G^2$. As another view, for bipartite graphs $H_1$ and $H_2$ and a positive integer $m$, the $m$-bipartite Ramsey number $BR_m(H_1, H_2)$ of $H_1$ and $H_2$ is the least integer $n$ $(n\geq m)$ such that every subgraph $G$ of $K_{m,n}$ results in $H_1\subseteq G$ or $H_2\subseteq \overline{G}$. The size of $m$-bipartite Ramsey number $BR_m(K_{2,2}, K_{2,2})$, the size of $m$-bipartite Ramsey number $BR_m(K_{2,2}, K_{3,3})$ and the size of $m$-bipartite Ramsey number $BR_m(K_{3,3}, K_{3,3})$ have been computed in several articles up to now. In this paper we determine the exact value of $BR_m(K_{2,2}, K_{4,4})$ for each $m\geq 2$.
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja