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: 18

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  matching
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Mean value for the matching and dominating polynomial

100%
Arocha J., Llano B.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 1
57-69
EN
The mean value of the matching polynomial is computed in the family of all labeled graphs with n vertices. We introduce the dominating polynomial of a graph whose coefficients enumerate the dominating sets for a graph and study some properties of the polynomial. The mean value of this polynomial is determined in a certain special family of bipartite digraphs.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Paired-domination

100%
Fitzpatrick S., Hartnell B.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
63-72
EN
We are interested in dominating sets (of vertices) with the additional property that the vertices in the dominating set can be paired or matched via existing edges in the graph. This could model the situation of guards or police where each has a partner or backup. This paper will focus on those graphs in which the number of matched pairs of a minimum dominating set of this type equals the size of some maximal matching in the graph. In particular, we characterize the leafless graphs of girth seven or more of this type.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Effect of edge-subdivision on vertex-domination in a graph

100%
Bhattacharya A., Vijayakumar G.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
335-347
EN
Let G be a graph with Δ(G) > 1. It can be shown that the domination number of the graph obtained from G by subdividing every edge exactly once is more than that of G. So, let ξ(G) be the least number of edges such that subdividing each of these edges exactly once results in a graph whose domination number is more than that of G. The parameter ξ(G) is called the subdivision number of G. This notion has been introduced by S. Arumugam and S. Velammal. They have conjectured that for any graph G with Δ(G) > 1, ξ(G) ≤ 3. We show that the conjecture is false and construct for any positive integer n ≥ 3, a graph G of order n with ξ(G) > [1/3]log₂ n. The main results of this paper are the following: (i) For any connected graph G with at least three vertices, ξ(G) ≤ γ(G)+1 where γ(G) is the domination number of G. (ii) If G is a connected graph of sufficiently large order n, then ξ(G) ≤ 4√n ln n+5
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On k-factor-critical graphs

100%
Favaron O.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 1
41-51
EN
A graph is said to be k-factor-critical if the removal of any set of k vertices results in a graph with a perfect matching. We study some properties of k-factor-critical graphs and show that many results on q-extendable graphs can be improved using this concept.
5
Content available remote

Edge Dominating Sets and Vertex Covers

100%
Dutton R., Klostermeyer W. F.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
437-456
EN
Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Clique packings and clique partitions of graphs without odd chordless cycles

100%
Lonc Z.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 2
143-149
EN
In this paper we consider partitions (resp. packings) of graphs without odd chordless cycles into cliques of order at least 2. We give a structure theorem, min-max results and characterization theorems for this kind of partitions and packings.
7
Content available remote

Optimal Backbone Coloring of Split Graphs with Matching Backbones

100%
Turowski K.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
157-169
EN
For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c : V (G) → N+ such that |c(u) − c(v)| ≥ 2 for each edge {u, v} ∈ E(H) and |c(u) − c(v)| ≥ 1 for each edge {u, v} ∈ E(G). The backbone chromatic number BBC(G,H) is the smallest integer k such that there exists a backbone coloring with maxv∈V (G) c(v) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
8
Content available remote

The Graphs Whose Permanental Polynomials Are Symmetric

100%
Li W.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
233-243
EN
The permanental polynomial [...] π(G,x)=∑i=0nbixn−i $\pi (G,x) = \sum\nolimits_{i = 0}^n {b_i x^{n - i} }$ of a graph G is symmetric if bi = bn−i for each i. In this paper, we characterize the graphs with symmetric permanental polynomials. Firstly, we introduce the rooted product H(K) of a graph H by a graph K, and provide a way to compute the permanental polynomial of the rooted product H(K). Then we give a sufficient and necessary condition for the symmetric polynomial, and we prove that the permanental polynomial of a graph G is symmetric if and only if G is the rooted product of a graph by a path of length one.
9
Content available remote

Matchings Extend to Hamiltonian Cycles in 5-Cube

100%
Wang F., Zhao W.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
217-231
EN
Ruskey and Savage asked the following question: Does every matching in a hypercube Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n ∈ {2, 3, 4}. In this paper, we prove that every matching in Q5 can be extended to a Hamiltonian cycle of Q5.
10
Content available remote

Fault diagnosis of a water for injection system using enhanced structural isolation

100%
Laursen M., Blanke M., Düştegör D.
International Journal of Applied Mathematics and Computer Science
|
2008
|
tom 18
|
nr 4
593-603
EN
A water for injection system supplies chilled sterile water as a solvent for pharmaceutical products. There are ultimate requirements for the quality of the sterile water, and the consequence of a fault in temperature or in flow control within the process may cause a loss of one or more batches of the production. Early diagnosis of faults is hence of considerable interest for this process. This study investigates the properties of multiple matchings with respect to isolability, and it suggests to explore the topologies of multiple use-modes for the process and to employ active techniques for fault isolation to enhance structural isolability of faults. The suggested methods are validated on a high-fidelity simulation of the process.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

100%
Broersma H., Marchal B., Paulusma D., Salman A.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 1
143-162
EN
We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. The main outcome of earlier studies is that the minimum number l of colors, for which such colorings V→ {1,2,...,l} exist, in the worst case is a factor times the chromatic number (for path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, l is at most a small additive constant (depending on λ) higher than the chromatic number. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on l than the previously known bounds.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Adjacent vertex distinguishing edge colorings of the direct product of a regular graph by a path or a cycle

100%
Frigerio L., Lastaria F., Salvi N.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
547-557
EN
In this paper we investigate the minimum number of colors required for a proper edge coloring of a finite, undirected, regular graph G in which no two adjacent vertices are incident to edges colored with the same set of colors. In particular, we study this parameter in relation to the direct product of G by a path or a cycle.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Sharp bounds for the number of matchings in generalized-theta-graphs

100%
Dolati A., Golalizadeh S.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
771-782
EN
A generalized-theta-graph is a graph consisting of a pair of end vertices joined by k (k ≥ 3) internally disjoint paths. We denote the family of all the n-vertex generalized-theta-graphs with k paths between end vertices by Θⁿₖ. In this paper, we determine the sharp lower bound and the sharp upper bound for the total number of matchings of generalized-theta-graphs in Θⁿₖ. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Matchings and total domination subdivision number in graphs with few induced 4-cycles

100%
Favaron O., Karami H., Khoeilar R., Sheikholeslami S.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
611-618
EN
A set S of vertices of a graph G = (V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $sd_{γₜ(G)}$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial Optimization, to appear) conjectured that: For any connected graph G of order n ≥ 3, $sd_{γₜ(G)} ≤ γₜ(G)+1$. In this paper we use matchings to prove this conjecture for graphs with at most three induced 4-cycles through each vertex.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Lower bounds for the domination number

100%
Delaviña E., Pepper R., Waller B.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 3
475-487
EN
In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.
16
Content available remote

Minimal fixed point sets of relative maps

88%
Zhao X. Z.
Fundamenta Mathematicae
|
1999
|
tom 162
|
nr 2
163-180
EN
Let f: (X,A) → (X,A) be a self map of a pair of compact polyhedra. It is known that f has at least N(f;X,A) fixed points on X. We give a sufficient and necessary condition for a finite set P (|P| = N(f;X,A)) to be the fixed point set of a map in the relative homotopy class of the given map f. As an application, a new lower bound for the number of fixed points of f on Cl(X-A) is given.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some maximum multigraphs and edge/vertex distance colourings

75%
Skupień Z.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 1
89-106
EN
Shannon-Vizing-type problems concerning the upper bound for a distance chromatic index of multigraphs G in terms of the maximum degree Δ(G) are studied. Conjectures generalizing those related to the strong chromatic index are presented. The chromatic d-index and chromatic d-number of paths, cycles, trees and some hypercubes are determined. Among hypercubes, however, the exact order of their growth is found.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some recent results on domination in graphs

75%
Plummer M.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
457-474
EN
In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; (3) upper bounds on the domination number of cubic graphs; and (4) upper bounds on the domination number of graphs embedded in surfaces.
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ć.