Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 8

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  regular graph
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Smallest Regular Graphs of Given Degree and Diameter

100%
Knor M.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 1
187-191
EN
In this note we present a sharp lower bound on the number of vertices in a regular graph of given degree and diameter.
2
Content available remote

Maximum Hypergraphs without Regular Subgraphs

100%
Kim J., Kostochka A. V.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 1
151-166
EN
We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n−1+r−2 edges. We conjecture that if n > r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, 2n−1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n > r cannot be weakened.
3
Content available remote

Splitting Cubic Circle Graphs

100%
Traldi L.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
723-741
EN
We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.
4
Content available remote

Various Bounds for Liar’s Domination Number

100%
Alimadadi A., Mojdeh D. A., Rad N. J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
629-641
EN
Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly identified as an intruder location under these restrictions. The minimum cardinality of a liar’s dominating set is called the liar’s domination number, and is denoted by γLR(G). In this paper, we present sharp bounds for the liar’s domination number in terms of the diameter, the girth and clique covering number of a graph. We present two Nordhaus-Gaddum type relations for γLR(G), and study liar’s dominating set sensitivity versus edge-connectivity. We also present various bounds for the liar’s domination component number, that is, the maximum number of components over all minimum liar’s dominating sets.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Interval edge colorings of some products of graphs

100%
Petrosyan P.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
357-373
EN
An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ {1,2,...,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ 𝔑, then the Cartesian product of these graphs belongs to 𝔑. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if G ∈ 𝔑, then G[nK₁] ∈ 𝔑 for any n ∈ ℕ. Furthermore, we show that if G,H ∈ 𝔑 and H is a regular graph, then strong and lexicographic products of graphs G,H belong to 𝔑. We also prove that tensor and strong tensor products of graphs G,H belong to 𝔑 if G ∈ 𝔑 and H is a regular graph.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Erdős regular graphs of even degree

88%
Dobrynin A., Mel'nikov L., Pyatkin A.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 2
269-279
EN
In 1960, Dirac put forward the conjecture that r-connected 4-critical graphs exist for every r ≥ 3. In 1989, Erdös conjectured that for every r ≥ 3 there exist r-regular 4-critical graphs. A method for finding r-regular 4-critical graphs and the numbers of such graphs for r ≤ 10 have been reported in [6,7]. Results of a computer search for graphs of degree r = 12,14,16 are presented. All the graphs found are both r-regular and r-connected.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Arboreal structure and regular graphs of median-like classes

75%
Brešar B.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
215-225
EN
We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of the gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph of the graph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization of analogous procedure in median graphs. We characterize regular graphs of these classes whenever they enjoy an additional property. As a corollary we derive that regular weakly median graphs are precisely Cartesian products in which each factor is a complete graph or a hyperoctahedron.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Certain new M-matrices and their properties with applications

75%
Mohan R., Kageyama S., Lee M., Yang G.
Discussiones Mathematicae Probability and Statistics
|
2008
|
tom 28
|
nr 2
183-207
EN
The Mₙ-matrix was defined by Mohan [21] who has shown a method of constructing (1,-1)-matrices and studied some of their properties. The (1,-1)-matrices were constructed and studied by Cohn [6], Ehrlich [9], Ehrlich and Zeller [10], and Wang [34]. But in this paper, while giving some resemblances of this matrix with a Hadamard matrix, and by naming it as an M-matrix, we show how to construct partially balanced incomplete block designs and some regular graphs by it. Two types of these M-matrices have been considered. Also we will make a mention of certain applications of these M-matrices in signal and communication processing, and network systems and end with some open problems.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.