All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 47

Showing per page

On composition of signed graphs

K. Shahul Hameed, K.A. Germina (2012)

Discussiones Mathematicae Graph Theory

A graph whose edges are labeled either as positive or negative is called a signed graph. In this article, we extend the notion of composition of (unsigned) graphs (also called lexicographic product) to signed graphs. We employ Kronecker product of matrices to express the adjacency matrix of this product of two signed graphs and hence find its eigenvalues when the second graph under composition is net-regular. A signed graph is said to be net-regular if every vertex has constant net-degree, namely,...

On •-Line Signed Graphs L•(S)

Deepa Sinha, Ayushi Dhama (2015)

Discussiones Mathematicae Graph Theory

A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the...

On Maximum Weight of a Bipartite Graph of Given Order and Size

Mirko Horňák, Stanislav Jendrol’, Ingo Schiermeyer (2013)

Discussiones Mathematicae Graph Theory

The weight of an edge xy of a graph is defined to be the sum of degrees of the vertices x and y. The weight of a graph G is the minimum of weights of edges of G. More than twenty years ago Erd˝os was interested in finding the maximum weight of a graph with n vertices and m edges. This paper presents a complete solution of a modification of the above problem in which a graph is required to be bipartite. It is shown that there is a function w*(n,m) such that the optimum weight is either w*(n,m) or...

On the Weight of Minor Faces in Triangle-Free 3-Polytopes

Oleg V. Borodin, Anna O. Ivanova (2016)

Discussiones Mathematicae Graph Theory

The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.

Reconstructibility of Boolean control networks with time delays in states

Ping Sun, Lijun Zhang, Kuize Zhang (2018)

Kybernetika

This paper deals with the reconstructibility of Boolean control networks (BCNs) with time delays in states. First, a survey on the semi-tensor product, weighted pair graph, constructed forest and finite automata is given. Second, by using the weighted pair graph, constructed forest and finite automata, an algorithm is designed to judge whether a Boolean control network with time delays in states is reconstructable or not under a mild assumption. Third, an algorithm is proposed to determine the current...

Signed degree sets in signed graphs

Shariefuddin Pirzada, T. A. Naikoo, F. A. Dar (2007)

Czechoslovak Mathematical Journal

The set D of distinct signed degrees of the vertices in a signed graph G is called its signed degree set. In this paper, we prove that every non-empty set of positive (negative) integers is the signed degree set of some connected signed graph and determine the smallest possible order for such a signed graph. We also prove that every non-empty set of integers is the signed degree set of some connected signed graph.

Signed domination and signed domatic numbers of digraphs

Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Let D be a finite and simple digraph with the vertex set V(D), and let f:V(D) → -1,1 be a two-valued function. If ∑ x ∈ N ¯ [ v ] f ( x ) ≥ 1 for each v ∈ V(D), where N¯[v] consists of v and all vertices of D from which arcs go into v, then f is a signed dominating function on D. The sum f(V(D)) is called the weight w(f) of f. The minimum of weights w(f), taken over all signed dominating functions f on D, is the signed domination number γ S ( D ) of D. A set f ₁ , f ₂ , . . . , f d of signed dominating functions on D with the property that ∑ i = 1 d f i ( x ) ≤ 1 for each...

Signed graphs with at most three eigenvalues

Farzaneh Ramezani, Peter Rowlinson, Zoran Stanić (2022)

Czechoslovak Mathematical Journal

We investigate signed graphs with just 2 or 3 distinct eigenvalues, mostly in the context of vertex-deleted subgraphs, the join of two signed graphs or association schemes.

Some results on semi-total signed graphs

Deepa Sinha, Pravin Garg (2011)

Discussiones Mathematicae Graph Theory

A signed graph (or sigraph in short) is an ordered pair S = ( S u , σ ) , where S u is a graph G = (V,E), called the underlying graph of S and σ:E → +, - is a function from the edge set E of S u into the set +,-, called the signature of S. The ×-line sigraph of S denoted by L × ( S ) is a sigraph defined on the line graph L ( S u ) of the graph S u by assigning to each edge ef of L ( S u ) , the product of signs of the adjacent edges e and f in S. In this paper, first we define semi-total line sigraph and semi-total point sigraph of a given...

The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs

Daniel W. Cranston, Sogol Jahanbekam, Douglas B. West (2014)

Discussiones Mathematicae Graph Theory

The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures...

The compositional construction of Markov processes II

L. de Francesco Albasini, N. Sabadini, R. F. C. Walters (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We add sequential operations to the categorical algebra of weighted and Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters, 
arXiv:0909.4136]. The extra expressiveness of the algebra permits the description of hierarchical systems, and ones with evolving geometry. We make a comparison with the probabilistic automata of Lynch et al. [SIAM J. Comput. 37 (2007) 977–1013].

The compositional construction of Markov processes II

L. de Francesco Albasini, N. Sabadini, R. F.C. Walters (2011)

RAIRO - Theoretical Informatics and Applications

We add sequential operations to the categorical algebra of weighted and Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters, 
arXiv:0909.4136]. The extra expressiveness of the algebra permits the description of hierarchical systems, and ones with evolving geometry. We make a comparison with the probabilistic automata of Lynch et al. [SIAM J. Comput.37 (2007) 977–1013].

Currently displaying 21 – 40 of 47