Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "Graph" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-25 z 960
Tytuł:
Pₘ-saturated bipartite graphs with minimum size
Autorzy:
Dudek, Aneta
Wojda, A.
Powiązania:
https://bibliotekanauki.pl/articles/744479.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
saturated graph
extremal graph
bipartite graph
Opis:
A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 2; 197-211
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Pm-saturated graphs with minimum size
Autorzy:
Dudek, A.
Wojda, A.P.
Powiązania:
https://bibliotekanauki.pl/articles/2050147.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
graph
saturated graph
extremal graph
Opis:
By Pm we denote a path of order m. A graph G is saidto be P$\text{}_{m}$ - saturated if G has no subgraph isomorphic to P$\text{}_{m}$ and adding any new edge to G creates a Pm in G. In 1986 L. Kaszonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size $sat(n; P\text{}_{m}$) of P$\text{}_{m}$-saturated graph and characterize the graphs of $Sat(n; P\text{}_{m}$) - the set of P$\text{}_{m}$-saturated graphs of minimum size. They have solved this problem for $n \geq a_{m}$ where $$ a_{m} = \begin{cases} 3 \cdot 2^{k-1} - 2~~\text{if}~m = 2k,k~~~~~~~\\ 2^{k+1} - 2~~~~~~\text{if}~m = 2k + 1, k \geq 2 \end{cases} $$ We define $$ b_{m} = \begin{cases} 3 \cdot 2^{k-2}~~~~~~~\text{if}~m = 2k,k \geq 3 \\ 3 \cdot 2 ^{k-1} - 1~~\text{if}~m = 2k + 1,k \geq 3 \end{cases} $$ and give $sat(n; P\text{}_{m}$) and $Sat(n; P\text{}_{m})$ for $m \geq 6$ and $b_{m} \leq n < a_{m}$
Źródło:
Opuscula Mathematica; 2004, 24, 1; 43-55
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on Total Graphs
Autorzy:
Forouhandeh, S.F.
Jafari Rad, N.
Vaqari Motlagh, B.H.
Patil, H.P.
Pandiya Raj, R.
Powiązania:
https://bibliotekanauki.pl/articles/31339326.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total graph
central graph
middle graph
Mycielski graph
Opis:
Erratum Identification and corrections of the existing mistakes in the paper On the total graph of Mycielski graphs, central graphs and their covering numbers, Discuss. Math. Graph Theory 33 (2013) 361-371.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 585-587
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The edge C₄ graph of some graph classes
Autorzy:
Menon, Manju
Vijayakumar, A.
Powiązania:
https://bibliotekanauki.pl/articles/744285.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge C₄ graph
threshold graph
block graph
geodetic graph
weakly geodetic graph
Opis:
The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices, there exists a super graph H such that C(H) = G and C(E₄(H)) = E₄(G). Also we give forbidden subgraph characterizations for E₄(G) being a threshold graph, block graph, geodetic graph and weakly geodetic graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 3; 365-375
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs
Autorzy:
Bašić, Nino
Fowler, Patrick W.
Pisanski, Tomaž
Sciriha, Irene
Powiązania:
https://bibliotekanauki.pl/articles/32222533.pdf
Data publikacji:
2022-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
signed graph
nut graph
singular graph
graph spectrum
Fowler construction
sign-balanced graph
sign-unbalanced graph
cocktail-party graph
Opis:
A signed graph has edge weights drawn from the set {+1, −1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller ‘seed’ graph, giving infinite series of both sign-balanced and sign-unbalanced ρ -regular nut graphs. Orders for which a regular nut graph with ρ = n − 1 exists are characterised; they are sign-unbalanced with an underlying graph Kn for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n − 2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1351-1382
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
(H,k) stable graphs with minimum size
Autorzy:
Dudek, Aneta
Szymański, Artur
Zwonek, Małgorzata
Powiązania:
https://bibliotekanauki.pl/articles/743537.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
stable graph
Opis:
Let us call a G (H,k) graph vertex stable if it contains a subgraph H ever after removing any of its k vertices. By Q(H,k) we will denote the minimum size of an (H,k) vertex stable graph. In this paper, we are interested in finding Q(₃,k), Q(₄,k), $Q(K_{1,p},k)$ and Q(Kₛ,k).
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 137-149
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The i-chords of cycles and paths
Autorzy:
McKee, Terry
Powiązania:
https://bibliotekanauki.pl/articles/743264.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chord
chordal graph
strongly chordal graph
ptolemaic graph
trivially perfect graph
threshold graph
Opis:
An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path P with |V(P)| ≥ i has an (i -2)-chord.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 607-615
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
4-chromatic Koester graphs
Autorzy:
Dobrynin, Andrey
Mel'nikov, Leonid
Powiązania:
https://bibliotekanauki.pl/articles/743274.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graph
4-critical graph
Grötzsch-Sachs graph
Koester graph
Opis:
Let G be a simple 4-regular plane graph and let S be a decomposition of G into edge-disjoint cycles. Suppose that every two adjacent edges on a face belong to different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Studies of coloring of graphs of this kind were originated by Grötzsch. Two 4-chromatic graphs generated by circles in the plane were constructed by Koester in 1984 [10,11,12]. Until now, no other examples of such graphs were known. We present fourteen new 4-chromatic graphs generated by circles in the plane.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 617-627
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Clique graph representations of ptolemaic graphs
Autorzy:
McKee, Terry
Powiązania:
https://bibliotekanauki.pl/articles/744102.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Ptolemaic graph
clique graph
chordal graph
clique tree
graph representation
Opis:
A graph is ptolemaic if and only if it is both chordal and distance-hereditary. Thus, a ptolemaic graph G has two kinds of intersection graph representations: one from being chordal, and the other from being distance-hereditary. The first of these, called a clique tree representation, is easily generated from the clique graph of G (the intersection graph of the maximal complete subgraphs of G). The second intersection graph representation can also be generated from the clique graph, as a very special case of the main result: The maximal Pₙ-free connected induced subgraphs of the p-clique graph of a ptolemaic graph G correspond in a natural way to the maximal $P_{n+1}$-free induced subgraphs of G in which every two nonadjacent vertices are connected by at least p internally disjoint paths.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 651-661
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Digraphs with isomorphic underlying and domination graphs: connected $UG^c(d)$
Autorzy:
Factor, Kim
Langley, Larry
Powiązania:
https://bibliotekanauki.pl/articles/743665.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination graph
domination
graph isomorphism
underlying graph
Opis:
The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 51-67
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
Autorzy:
Czap, Július
Przybyło, Jakub
Škrabuľáková, Erika
Powiązania:
https://bibliotekanauki.pl/articles/31341143.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
1-planar graph
bipartite graph
graph size
Opis:
A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets. Bipartite 1-planar graphs are known to have at most 3n − 8 edges, where n denotes the order of a graph. We show that maximal-size bipartite 1-planar graphs which are almost balanced have not significantly fewer edges than indicated by this upper bound, while the same is not true for unbalanced ones. We prove that the maximal possible size of bipartite 1-planar graphs whose one partite set is much smaller than the other one tends towards 2n rather than 3n. In particular, we prove that if the size of the smaller partite set is sublinear in n, then |E| = (2 + o(1))n, while the same is not true otherwise.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 141-151
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Existence of Regular Nut Graphs for Degree at Most 11
Autorzy:
Fowler, Patrick W.
Gauci, John Baptist
Goedgebeur, Jan
Pisanski, Tomaž
Sciriha, Irene
Powiązania:
https://bibliotekanauki.pl/articles/31550028.pdf
Data publikacji:
2020-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
nut graph
core graph
regular graph
nullity
Opis:
A nut graph is a singular graph with one-dimensional kernel and corresponding eigenvector with no zero elements. The problem of determining the orders n for which d-regular nut graphs exist was recently posed by Gauci, Pisanski and Sciriha. These orders are known for d ≤ 4. Here we solve the problem for all remaining cases d ≤ 11 and determine the complete lists of all d-regular nut graphs of order n for small values of d and n. The existence or non-existence of small regular nut graphs is determined by a computer search. The main tool is a construction that produces, for any d-regular nut graph of order n, another d-regular nut graph of order n+2d. If we are given a sufficient number of d-regular nut graphs of consecutive orders, called seed graphs, this construction may be applied in such a way that the existence of all d-regular nut graphs of higher orders is established. For even d the orders n are indeed consecutive, while for odd d the orders n are consecutive even numbers. Furthermore, necessary conditions for combinations of order and degree for vertex-transitive nut graphs are derived.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 2; 533-557
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dualizing Distance-Hereditary Graphs
Autorzy:
McKee, Terry A.
Powiązania:
https://bibliotekanauki.pl/articles/32083836.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
distance-hereditary graph
dual graph
graph duality
Opis:
Distance-hereditary graphs can be characterized by every cycle of length at least 5 having crossing chords. This makes distance-hereditary graphs susceptible to dualizing, using the common extension of geometric face/vertex planar graph duality to cycle/cutset duality as in abstract matroidal duality. The resulting “DH* graphs” are characterized and then analyzed in terms of connectivity. These results are used in a special case of plane-embedded graphs to justify viewing DH* graphs as the duals of distance-hereditary graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 285-296
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge cycle extendable graphs
Autorzy:
McKee, Terry
Powiązania:
https://bibliotekanauki.pl/articles/743340.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cycle extendable graph
chordal graph
chordless graph
minimally 2-connected graph
Opis:
A graph is edge cycle extendable if every cycle C that is formed from edges and one chord of a larger cycle C⁺ is also formed from edges and one chord of a cycle C' of length one greater than C with V(C') ⊆ V(C⁺). Edge cycle extendable graphs are characterized by every block being either chordal (every nontriangular cycle has a chord) or chordless (no nontriangular cycle has a chord); equivalently, every chord of a cycle of length five or more has a noncrossing chord.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 2; 373-378
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the 12-Representability of Induced Subgraphs of a Grid Graph
Autorzy:
Chen, Joanna N.
Kitaev, Sergey
Powiązania:
https://bibliotekanauki.pl/articles/32361728.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph representation
12-representable graph
grid graph
forbidden subgraph
square grid graph
line grid graph
Opis:
The notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53]. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12- representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question of Jones et al. is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al. by providing a complete characterization of 12-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 383-403
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
α2-labeling of graphs
Autorzy:
Froncek, D.
Powiązania:
https://bibliotekanauki.pl/articles/255852.pdf
Data publikacji:
2009
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
graph decomposition
graph labeling
Opis:
We show that if a graph G on n edges allows certain special type of rosy labeling (a.k.a. rho;-labeling), called α2-labeling, then for any positive integer k the complete graph K2nk+1 can be decomposed into copies of G. This notion generalizes the α-labeling introduced in 1967 by A. Rosa.
Źródło:
Opuscula Mathematica; 2009, 29, 4; 393-397
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Product rosy labeling of graphs
Autorzy:
Fronček, Dalibor
Powiązania:
https://bibliotekanauki.pl/articles/743046.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph decomposition
graph labeling
Opis:
In this paper we describe a natural extension of the well-known ρ-labeling of graphs (also known as rosy labeling). The labeling, called product rosy labeling, labels vertices with elements of products of additive groups. We illustrate the usefulness of this labeling by presenting a recursive construction of infinite families of trees decomposing complete graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 3; 431-439
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
(H,k) stable bipartite graphs with minimum size
Autorzy:
Dudek, Aneta
Zwonek, Małgorzata
Powiązania:
https://bibliotekanauki.pl/articles/744467.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
vertex stable graph
Opis:
Let us call a graph G(H;k) vertex stable if it contains a subgraph H after removing any of its k vertices. In this paper we are interested in finding the $(K_{n,n+1};1)$ (respectively $(K_{n,n};1)$) vertex stable graphs with minimum size.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 3; 573-581
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decomposition of complete graphs into small graphs
Autorzy:
Froncek, D.
Powiązania:
https://bibliotekanauki.pl/articles/255502.pdf
Data publikacji:
2010
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
graph decomposition
graph labeling
Opis:
In 1967, A. Rosa proved that if a bipartite graph G with n edges has an α-labeling, then for any positive integer p the complete graph K(2np+1) can be cyclically decomposed into copies of G. This has become a part of graph theory folklore since then. In this note we prove a generalization of this result. We show that every bipartite graph H which decomposes K(k) and K(m) also decomposes K(km).
Źródło:
Opuscula Mathematica; 2010, 30, 3; 277-280
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A conjecture on the prevalence of cubic bridge graphs
Autorzy:
Filar, Jerzy
Haythorpe, Michael
Nguyen, Giang
Powiązania:
https://bibliotekanauki.pl/articles/744564.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian graph
non-Hamiltonian graph
cubic bridge graph
Opis:
Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 175-179
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Turán Function and H-Decomposition Problem for Gem Graphs
Autorzy:
Liu, Henry
Sousa, Teresa
Powiązania:
https://bibliotekanauki.pl/articles/31342280.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
gem graph
Turán function
extremal graph
graph decomposition
Opis:
Given a graph H, the Turán function ex(n,H) is the maximum number of edges in a graph on n vertices not containing H as a subgraph. For two graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let ϕ(n,H) be the smallest number ϕ such that any graph G of order n admits an H-decomposition with at most ϕ parts. Pikhurko and Sousa conjectured that ϕ (n,H) = ex(n,H) for χ (H) ≥ 3 and all sufficiently large n. Their conjecture has been verified by Özkahya and Person for all edge-critical graphs H. In this article, we consider the gem graphs gem4 and gem5. The graph gem4 consists of the path P4 with four vertices a, b, c, d and edges ab, bc, cd plus a universal vertex u adjacent to a, b, c, d, and the graph gem5 is similarly defined with the path P5 on five vertices. We determine the Turán functions ex(n, gem4) and ex(n, gem5), and verify the conjecture of Pikhurko and Sousa when H is the graph gem4 and gem5.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 717-741
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterization of Line-Consistent Signed Graphs
Autorzy:
Slilaty, Daniel C.
Zaslavsky, Thomas
Powiązania:
https://bibliotekanauki.pl/articles/31339317.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
line-consistent signed graph
line graph
consistent vertex-signed graph
consistent marked graph
Opis:
The line graph of a graph with signed edges carries vertex signs. A vertex-signed graph is consistent if every circle (cycle, circuit) has positive vertex-sign product. Acharya, Acharya, and Sinha recently characterized line-consistent signed graphs, i.e., edge-signed graphs whose line graphs, with the naturally induced vertex signature, are consistent. Their proof applies Hoede’s relatively difficult characterization of consistent vertex-signed graphs. We give a simple proof that does not depend on Hoede’s theorem as well as a structural description of line-consistent signed graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 589-594
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hamiltonian and Pancyclic Graphs in the Class of Self-Centered Graphs with Radius Two
Autorzy:
Hrnčiar, Pavel
Monoszová, Gabriela
Powiązania:
https://bibliotekanauki.pl/articles/31342283.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
self-centered graph with radius 2
Hamiltonian graph
pancyclic graph
size of graph
Opis:
The paper deals with Hamiltonian and pancyclic graphs in the class of all self-centered graphs of radius 2. For both of the two considered classes of graphs we have done the following. For a given number n of vertices, we have found an upper bound of the minimum size of such graphs. For n ≤ 12 we have found the exact values of the minimum size. On the other hand, the exact value of the maximum size has been found for every n. Moreover, we have shown that such a graph (of order n and) of size m exists for every m between the minimum and the maximum size. For n ≤ 10 we have found all nonisomorphic graphs of the minimum size, and for n = 11 only for Hamiltonian graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 661-681
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Phylogeny Graphs of Doubly Partial Orders
Autorzy:
Park, Boram
Sano, Yoshio
Powiązania:
https://bibliotekanauki.pl/articles/29551728.pdf
Data publikacji:
2013-09-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
competition graph
phylogeny graph
doubly partial order
interval graph
Opis:
The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V (P(D)) := V (D) and E(P(D)) := {xy | N+D (x) ∩ N+D(y) ¹ ⊘ } ⋃ {xy | (x,y) ∈ A(D)}, where N+D(x):= {v ∈ V(D) | (x,v) ∈ A (D)}. In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph G̃, there exists an interval graph G such that G̃ contains the graph G as an induced subgraph and that G̃ is the phylogeny graph of a doubly partial order.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 657-664
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterizations of planar plick graphs
Autorzy:
Kulli, V.
Basavanagoud, B.
Powiązania:
https://bibliotekanauki.pl/articles/744402.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
inner vertex number
planar graph
line graph
plick graph
Opis:
In this paper we present characterizations of graphs whose plick graphs are planar, outerplanar and minimally nonouterplanar.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 41-45
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-25 z 960

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies